oj.uz

Submission #72391

# Submission time Handle Problem Language Result Execution time Memory
72391 2018-08-26T07:38:57 Z (#2175, xdoju, kazel, pps789) Gorgeous Pill (FXCUP3_gorgeous) C++14
51 / 100
 501 ms 14456 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

long long dp[2][1002][1002]; // 너비, 구간 시작점, 첫 약

int C[1002];
int D[1002];

int main(){
  int N; scanf("%d", &N);

  if(N > 1000){
    puts("Subtask 3");
    return 0;
  }

  for(int i = 1; i <= N; i++) scanf("%d", &C[i]);
  for(int i = 1; i <= N; i++) scanf("%d", &D[i]);

  for(int i = 1; i <= N; i++) dp[1][i][i] = (C[i] == 1 ? D[i] : 0);

  for(int w = 2; w <= N; w++){
    int w_ = w & 1, _w = w_ ^ 1;

    int e = N - w + 1;

    for(int i = 1; i <= e; i++){
      int fe = i + w - 1;

      for(int f = i; f <= fe; f++){
        // 마지막 약으로 구간의 시작점 or 구간의 끝점

        long long a = f < fe ? dp[_w][i][f] + (C[fe] == w ? D[fe] : 0) : 0;
        long long b = f > i ? dp[_w][i + 1][f] + (C[i] == w ? D[i] : 0) : 0;

        dp[w_][i][f] = max(a, b);
      }
    }
  }

  for(int i = 1; i <= N; i++) printf("%lld ", dp[N & 1][1][i]);

  printf("\n");
  return 0;
}

Compilation message

gorgeous.cpp: In function 'int main()':
gorgeous.cpp:11:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N; scanf("%d", &N);
          ~~~~~^~~~~~~~~~
gorgeous.cpp:18:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= N; i++) scanf("%d", &C[i]);
                               ~~~~~^~~~~~~~~~~~~
gorgeous.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i = 1; i <= N; i++) scanf("%d", &D[i]);
                               ~~~~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 680 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 3 ms 840 KB Output is correct
8 Correct 3 ms 1352 KB Output is correct
9 Correct 4 ms 1608 KB Output is correct
10 Correct 37 ms 4424 KB Output is correct
11 Correct 183 ms 10956 KB Output is correct
12 Correct 332 ms 13400 KB Output is correct
13 Correct 501 ms 14444 KB Output is correct
14 Correct 448 ms 14444 KB Output is correct
15 Correct 429 ms 14456 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 564 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 3 ms 840 KB Output is correct
8 Correct 3 ms 1352 KB Output is correct
9 Correct 4 ms 1608 KB Output is correct
10 Correct 37 ms 4424 KB Output is correct
11 Correct 183 ms 10956 KB Output is correct
12 Correct 332 ms 13400 KB Output is correct
13 Correct 501 ms 14444 KB Output is correct
14 Correct 448 ms 14444 KB Output is correct
15 Correct 429 ms 14456 KB Output is correct
16 Incorrect 2 ms 14456 KB Output isn't correct
17 Halted 0 ms 0 KB -