oj.uz

Submission #157323

# Submission time Handle Problem Language Result Execution time Memory
157323 2019-10-10T16:29:35 Z karma 스트랩 (JOI14_straps) C++14
55 / 100
 80 ms 31864 KB 
#include<bits/stdc++.h>
#define FileName      "test"
#define ll            long long
#define pb            emplace_back
#define deg           first
#define c             second

using namespace std;

typedef pair<int, int> pii;
const int N = int(2e3) + 2;
const int oo = int(2e9) + 7;

int f[N][N * 2], Max[N * 2], PMax[N * 2], a[N];
int n, m, res = 0, pre;
pii val[N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
       freopen(FileName".inp", "r", stdin);
       freopen(FileName".out", "w", stdout);
    }
    cin >> n; m = 2 * n + 1;
    for(int i = 1; i <= n; ++i) {
        cin >> val[i].deg >> val[i].c;
        fill(f[i], f[i] + m + 1, -oo);
    }
    sort(val + 1, val + n + 1, [](const pii& x, const pii& y) {
             return x.deg > y.deg;
         });
    fill(Max, Max + m + 1, -oo);
    fill(PMax, PMax + m + 1, -oo);
    f[0][1] = 0; PMax[1] = Max[1] = 0;
    for(int i = 1; i <= n; ++i) {
       for(int j = 0; j < m; ++j) {
          pre = min(j + 1 - val[i].deg, m - 1);
          if(pre <= 0 || Max[pre] == -oo) continue;
          res = max(res, (f[i][j] = Max[pre] + val[i].c));
       }
       pre = m + 1 - val[i].deg;
       if(pre > 0 && PMax[pre] != -oo) res = max(res, (f[i][m] = PMax[pre] + val[i].c));
       for(int j = 0; j <= m; ++j) Max[j] = max(Max[j], f[i][j]);
       for(int j = m; j >= 0; --j) PMax[j] = max(PMax[j + 1], Max[j]);
    }
    cout << res;
}
///2.21 - 996337317

Compilation message

straps.cpp: In function 'int main()':
straps.cpp:23:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".inp", "r", stdin);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
straps.cpp:24:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
        freopen(FileName".out", "w", stdout);
        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 424 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 380 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 3 ms 892 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 24 ms 12260 KB Output is correct
9 Correct 23 ms 12280 KB Output is correct
10 Correct 23 ms 12280 KB Output is correct
11 Correct 23 ms 12280 KB Output is correct
12 Correct 75 ms 31736 KB Output is correct
13 Correct 75 ms 31736 KB Output is correct
14 Correct 75 ms 31736 KB Output is correct
15 Correct 75 ms 31740 KB Output is correct
16 Correct 75 ms 31736 KB Output is correct
17 Correct 75 ms 31792 KB Output is correct
18 Correct 75 ms 31780 KB Output is correct
19 Correct 75 ms 31736 KB Output is correct
20 Correct 76 ms 31864 KB Output is correct
21 Correct 76 ms 31736 KB Output is correct
22 Correct 75 ms 31736 KB Output is correct
23 Correct 77 ms 31736 KB Output is correct
24 Correct 77 ms 31736 KB Output is correct
25 Correct 77 ms 31736 KB Output is correct
26 Correct 76 ms 31736 KB Output is correct
27 Correct 76 ms 31736 KB Output is correct
28 Correct 76 ms 31736 KB Output is correct
29 Correct 76 ms 31740 KB Output is correct
30 Correct 77 ms 31740 KB Output is correct
31 Correct 76 ms 31736 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 23 ms 12152 KB Output is correct
10 Correct 24 ms 12252 KB Output is correct
11 Correct 23 ms 12152 KB Output is correct
12 Correct 24 ms 12408 KB Output is correct
13 Correct 24 ms 12408 KB Output is correct
14 Correct 23 ms 12152 KB Output is correct
15 Correct 23 ms 12152 KB Output is correct
16 Correct 24 ms 12156 KB Output is correct
17 Correct 76 ms 31736 KB Output is correct
18 Correct 75 ms 31864 KB Output is correct
19 Correct 75 ms 31780 KB Output is correct
20 Correct 75 ms 31736 KB Output is correct
21 Correct 75 ms 31736 KB Output is correct
22 Correct 75 ms 31736 KB Output is correct
23 Correct 76 ms 31692 KB Output is correct
24 Correct 75 ms 31784 KB Output is correct
25 Correct 77 ms 31708 KB Output is correct
26 Correct 75 ms 31736 KB Output is correct
27 Correct 76 ms 31720 KB Output is correct
28 Correct 78 ms 31736 KB Output is correct
29 Correct 80 ms 31776 KB Output is correct
30 Correct 75 ms 31736 KB Output is correct
31 Correct 75 ms 31736 KB Output is correct
32 Correct 75 ms 31716 KB Output is correct
33 Correct 75 ms 31864 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 31864 KB Output is correct
2 Correct 75 ms 31816 KB Output is correct
3 Correct 75 ms 31776 KB Output is correct
4 Correct 75 ms 31848 KB Output is correct
5 Correct 77 ms 31776 KB Output is correct
6 Correct 76 ms 31816 KB Output is correct
7 Correct 76 ms 31740 KB Output is correct
8 Correct 77 ms 31844 KB Output is correct
9 Correct 78 ms 31864 KB Output is correct
10 Correct 78 ms 31716 KB Output is correct
11 Correct 77 ms 31740 KB Output is correct
12 Correct 77 ms 31736 KB Output is correct
13 Correct 76 ms 31736 KB Output is correct
14 Correct 76 ms 31736 KB Output is correct
15 Incorrect 77 ms 31736 KB Output isn't correct
16 Halted 0 ms 0 KB -