Submission #1005565


Source Code Expand

#include <bits/stdc++.h>

#define ll long long 
using namespace std;

int m;
deque < pair < ll, int > > d[320];

ll get(int k, int i)
{
    if(k == 0)
        return 0;
    while(d[k].front().second < i - m)
        d[k].pop_front();
    return d[k].front().first;
}

void ins(ll val, int i, int k)
{
    while(!d[k].empty() && d[k].back().first <= val)
        d[k].pop_back();
    d[k].push_back(make_pair(val, i));
}

int k, n;
ll a[100020], answer = 0;

int main() {
    scanf("%d %d %d", &n, &m, &k);
    
    for(int i = 1; i <= n; ++ i)
      scanf("%lld", &a[i]);
    
    for(int i = 1; i < k; ++ i)
      d[i].push_back(make_pair(-1e15, 0));
    for(int i = 1; i <= n; ++ i)
    {
        for(int j = k; j >= 1;  -- j)
        {
            ll p = get(j - 1, i);
            p += j * a[i];
            if(j == k)
                answer = max(answer, p);
            else
                ins(p, i, j);
        }
    }
    
    cout << answer << endl;
    return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User octopuses
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1027 Byte
Status AC
Exec Time 479 ms
Memory 1280 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:29:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
                                  ^
./Main.cpp:32:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%lld", &a[i]);
                           ^

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 100 / 100 200 / 200 300 / 300 100 / 100
Status
AC × 3
AC × 10
AC × 12
AC × 21
AC × 43
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
subtask3 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt
Case Name Status Exec Time Memory
sample_1.txt AC 3 ms 512 KB
sample_2.txt AC 3 ms 512 KB
sample_3.txt AC 3 ms 512 KB
subtask_1_1.txt AC 3 ms 512 KB
subtask_1_2.txt AC 43 ms 512 KB
subtask_1_3.txt AC 407 ms 1280 KB
subtask_1_4.txt AC 5 ms 512 KB
subtask_1_5.txt AC 20 ms 1280 KB
subtask_1_6.txt AC 3 ms 512 KB
subtask_1_7.txt AC 140 ms 1280 KB
subtask_1_8.txt AC 411 ms 1280 KB
subtask_1_9.txt AC 5 ms 512 KB
subtask_2_1.txt AC 3 ms 512 KB
subtask_2_2.txt AC 3 ms 512 KB
subtask_2_3.txt AC 3 ms 512 KB
subtask_2_4.txt AC 3 ms 512 KB
subtask_2_5.txt AC 3 ms 512 KB
subtask_2_6.txt AC 3 ms 512 KB
subtask_2_7.txt AC 3 ms 512 KB
subtask_2_8.txt AC 3 ms 512 KB
subtask_2_9.txt AC 3 ms 512 KB
subtask_3_1.txt AC 52 ms 1280 KB
subtask_3_2.txt AC 53 ms 1280 KB
subtask_3_3.txt AC 51 ms 1280 KB
subtask_3_4.txt AC 43 ms 1152 KB
subtask_3_5.txt AC 5 ms 512 KB
subtask_3_6.txt AC 37 ms 1280 KB
subtask_3_7.txt AC 52 ms 1280 KB
subtask_3_8.txt AC 8 ms 512 KB
subtask_3_9.txt AC 58 ms 1280 KB
subtask_4_1.txt AC 408 ms 1280 KB
subtask_4_10.txt AC 447 ms 1280 KB
subtask_4_11.txt AC 474 ms 1280 KB
subtask_4_12.txt AC 478 ms 1280 KB
subtask_4_13.txt AC 479 ms 1280 KB
subtask_4_2.txt AC 467 ms 1280 KB
subtask_4_3.txt AC 408 ms 1280 KB
subtask_4_4.txt AC 411 ms 1280 KB
subtask_4_5.txt AC 353 ms 1280 KB
subtask_4_6.txt AC 43 ms 1280 KB
subtask_4_7.txt AC 252 ms 1280 KB
subtask_4_8.txt AC 406 ms 1280 KB
subtask_4_9.txt AC 199 ms 1280 KB