Submission #997882


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

int N, M, K;
int A[100001];
long long dp[301][100001];

struct smax
{
    long long q[100001];
    int w[100001];
    int h, t;
    void clear()
    {
        h=t=0;
    }
    void append(long long a, int b)
    {
        while(h<t && q[t-1]<=a)
            t--;
        w[t]=b;
        q[t++]=a;
    }
    void filter(int x)
    {
        while(h<t && w[h]<x)
            h++;
    }
    long long getmax()
    {
        return q[h];
    }
} dq;

int main()
{
    scanf("%d%d%d", &N, &M, &K);
    for(int i=1; i<=N; i++)
        scanf("%d", A+i), dp[1][i]=A[i];
    for(int i=2; i<=K; i++)
    {
        dq.clear();
        dq.append(dp[i-1][i-1], i-1);
        for(int j=i; j<=N; j++)
        {
            dq.filter(j-M);
            dp[i][j]=dq.getmax()+1LL*A[j]*i;
            dq.append(dp[i-1][j], j);
        }
    }
    printf("%lld\n", *max_element(dp[K]+1, dp[K]+1+N));
    return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User FatalEagle
Language C++14 (GCC 5.4.1)
Score 700
Code Size 997 Byte
Status AC
Exec Time 557 ms
Memory 235648 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:32: 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:40:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i), dp[1][i]=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 2 ms 256 KB
sample_2.txt AC 2 ms 256 KB
sample_3.txt AC 2 ms 256 KB
subtask_1_1.txt AC 3 ms 384 KB
subtask_1_2.txt AC 58 ms 24576 KB
subtask_1_3.txt AC 537 ms 235008 KB
subtask_1_4.txt AC 6 ms 1664 KB
subtask_1_5.txt AC 22 ms 4608 KB
subtask_1_6.txt AC 4 ms 1152 KB
subtask_1_7.txt AC 190 ms 78720 KB
subtask_1_8.txt AC 541 ms 235008 KB
subtask_1_9.txt AC 6 ms 2304 KB
subtask_2_1.txt AC 3 ms 384 KB
subtask_2_2.txt AC 3 ms 384 KB
subtask_2_3.txt AC 3 ms 384 KB
subtask_2_4.txt AC 3 ms 384 KB
subtask_2_5.txt AC 3 ms 384 KB
subtask_2_6.txt AC 3 ms 384 KB
subtask_2_7.txt AC 3 ms 384 KB
subtask_2_8.txt AC 3 ms 384 KB
subtask_2_9.txt AC 3 ms 384 KB
subtask_3_1.txt AC 67 ms 24064 KB
subtask_3_2.txt AC 66 ms 24064 KB
subtask_3_3.txt AC 65 ms 23296 KB
subtask_3_4.txt AC 54 ms 19456 KB
subtask_3_5.txt AC 6 ms 1536 KB
subtask_3_6.txt AC 40 ms 12416 KB
subtask_3_7.txt AC 66 ms 24064 KB
subtask_3_8.txt AC 9 ms 2816 KB
subtask_3_9.txt AC 67 ms 24064 KB
subtask_4_1.txt AC 540 ms 235008 KB
subtask_4_10.txt AC 479 ms 235648 KB
subtask_4_11.txt AC 557 ms 235136 KB
subtask_4_12.txt AC 551 ms 235136 KB
subtask_4_13.txt AC 545 ms 235008 KB
subtask_4_2.txt AC 541 ms 235008 KB
subtask_4_3.txt AC 544 ms 235008 KB
subtask_4_4.txt AC 539 ms 235008 KB
subtask_4_5.txt AC 459 ms 199040 KB
subtask_4_6.txt AC 54 ms 18560 KB
subtask_4_7.txt AC 292 ms 124032 KB
subtask_4_8.txt AC 533 ms 232832 KB
subtask_4_9.txt AC 247 ms 103808 KB