Submission #1012477


Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;

int n, m, k;
ll a[111111];

ll dp[333][33];

ll dp2[2][333];

ll dp3[111111][333];
priority_queue<ll> q[333], dq[333];

ll dp4[333][111111];
int deq[333][111111];
int s[333], t[333];

struct S {
  
};

int main(void) {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; i++) {
    scanf("%lld", a+i);
  }
  if (n == m && false) {
    ll res = 0;
    memset(dp2, -1, sizeof(dp2));
    dp2[1][0] = 0;
    for (int i = 0; i < n; i++) {
      dp2[i%2][0] = 0;
      for (int j = 1; j <= k; j++) {
        if (dp2[i%2][j-1] >= 0) {
          dp2[(i+1)%2][j] = max({
                dp2[(i+1)%2][j],
                    dp2[i%2][j-1] + a[i]*j,
                    dp2[i%2][j]
                  });
        }
      }
      for (int j = 0; j <= k; j++) {
        res = max(res, dp2[(i+1)%2][j]);
        if (dp2[i%2][j] >= 0) {
          dp2[i%2][j] = 0;
        }
        // printf("%5lld", dp2[(i+1)%2][j]);
      }
      // puts("");
    }
    printf("%lld\n", res);
  } else if (n <= 300 && k <= 30 && false) {
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i <= n; i++) {
      dp[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < k; j++) {
        for (int l = 1; l <= m && i-l >= 0; l++) {
          if (dp[i-l][j] >= 0) {
            dp[i][j+1] = max(dp[i][j+1],
                             dp[i-l][j]+a[i-1]*(j+1));
          }
        }
      }
    }
    ll res = 0;
    for (int i = 0; i <= n+1; i++) {
      for (int j = 0; j <= k; j++) {
        // printf("%5lld", dp[i][j]);
        res = max(res, dp[i][j]);
      }
      // puts("");
    }
    printf("%lld\n", res);
  } else if (k <= 30 && false) {
    q[0].push(0);
    memset(dp3, -1, sizeof(dp3));
    for (int i = 1; i <= n; i++) {
      for (int j = k-1; j >= 0; j--) {
        if (q[j].size() == 0) continue;
        while (!dq[j].empty() && q[j].top() == dq[j].top()) {
          q[j].pop();
          dq[j].pop();
        }
        dp3[i][j+1] = q[j].top()+a[i-1]*(j+1);
        q[j+1].push(q[j].top()+a[i-1]*(j+1));
      }
      if (i-m >= 0) {
        for (int j = 0; j < k; j++) {
          if (dp3[i-m][j] >= 0) {
            dq[j].push(dp3[i-m][j]);
          }
        }
      }
    }
    printf("%lld\n", q[k].top());
  } else {
    memset(dp4, -1, sizeof(dp4));
    for (int i = 0; i <= n; i++) {
      dp4[0][i] = 0;
      deq[0][t[0]++] = 0;
    }
    ll res = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = k-1; j >= 0; j--) {
        if (s[j] < t[j]) {
          dp4[j+1][i] = dp4[j][deq[j][s[j]]] + a[i-1]*(j+1);
          res = max(res, dp4[j+1][i]);
          // printf("%d %d max: %lld\n", i, j, dp4[j][deq[j][s[j]]]);
          while (s[j+1] < t[j+1] &&
                 dp4[j+1][deq[j+1][t[j+1]-1]] <= dp4[j+1][i]) --t[j+1];
          deq[j+1][t[j+1]++] = i;
          if (i-m >= 0) {
            if (j > 0 && deq[j][s[j]] == i-m) {
              ++s[j];
            }
          }
        }
      }
    }
    /*
    for (int ii = 0; ii <= k; ii++) {
      for (int jj = 0; jj <= n; jj++) {
        printf("%5lld", dp4[ii][jj]);
      }
      puts("");
    }
    // */
    printf("%lld\n", res);
  }
  return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User roxion1377
Language C++14 (GCC 5.4.1)
Score 700
Code Size 3426 Byte
Status AC
Exec Time 1154 ms
Memory 408320 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:30:30: 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:23: 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 334 ms 289280 KB
sample_2.txt AC 334 ms 289280 KB
sample_3.txt AC 338 ms 289408 KB
subtask_1_1.txt AC 335 ms 289536 KB
subtask_1_2.txt AC 402 ms 290688 KB
subtask_1_3.txt AC 1149 ms 291712 KB
subtask_1_4.txt AC 335 ms 289536 KB
subtask_1_5.txt AC 354 ms 290560 KB
subtask_1_6.txt AC 339 ms 290176 KB
subtask_1_7.txt AC 487 ms 290944 KB
subtask_1_8.txt AC 1140 ms 291712 KB
subtask_1_9.txt AC 344 ms 290560 KB
subtask_2_1.txt AC 336 ms 289408 KB
subtask_2_2.txt AC 337 ms 289536 KB
subtask_2_3.txt AC 336 ms 289408 KB
subtask_2_4.txt AC 337 ms 289408 KB
subtask_2_5.txt AC 334 ms 289408 KB
subtask_2_6.txt AC 337 ms 289408 KB
subtask_2_7.txt AC 335 ms 289408 KB
subtask_2_8.txt AC 338 ms 289408 KB
subtask_2_9.txt AC 333 ms 289408 KB
subtask_3_1.txt AC 380 ms 290560 KB
subtask_3_2.txt AC 381 ms 290560 KB
subtask_3_3.txt AC 376 ms 290560 KB
subtask_3_4.txt AC 373 ms 290432 KB
subtask_3_5.txt AC 339 ms 289536 KB
subtask_3_6.txt AC 365 ms 290560 KB
subtask_3_7.txt AC 378 ms 290560 KB
subtask_3_8.txt AC 352 ms 289536 KB
subtask_3_9.txt AC 374 ms 290688 KB
subtask_4_1.txt AC 1154 ms 291712 KB
subtask_4_10.txt AC 1106 ms 408320 KB
subtask_4_11.txt AC 931 ms 301824 KB
subtask_4_12.txt AC 935 ms 296704 KB
subtask_4_13.txt AC 953 ms 293632 KB
subtask_4_2.txt AC 1007 ms 292224 KB
subtask_4_3.txt AC 1135 ms 291712 KB
subtask_4_4.txt AC 1148 ms 291712 KB
subtask_4_5.txt AC 954 ms 291584 KB
subtask_4_6.txt AC 367 ms 290560 KB
subtask_4_7.txt AC 550 ms 291328 KB
subtask_4_8.txt AC 1130 ms 291712 KB
subtask_4_9.txt AC 532 ms 291072 KB