oj.uz

Submission #157315

# Submission time Handle Problem Language Result Execution time Memory
157315 2019-10-10T15:48:06 Z karma 스트랩 (JOI14_straps) C++14
45 / 100
 27 ms 16148 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], Max[N];
int n, a[N], res = 0;
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;
    for(int i = 1; i <= n; ++i) {
        cin >> val[i].deg >> val[i].c;
        fill(f[i], f[i] + n + 1, -oo);
    }
    sort(val + 1, val + n + 1, [](const pii& x, const pii& y) {
             return x.deg > y.deg;
         });
    /// f(i, j) = max niem vui khi den cai thu i va co j cong ket noi
    fill(Max, Max + n + 1, -oo);
    f[0][1] = 0; Max[1] = 0;
    for(int i = 1; i <= n; ++i) {
       for(int j = 0; j <= n; ++j) {
          int pre = min(j + 1 - val[i].deg, n);
          if(pre < 0) continue;
          res = max(res, (f[i][j] = Max[pre] + val[i].c));
       }
       for(int j = 0; j <= n; ++j) Max[j] = max(Max[j], f[i][j]);
    }
    cout << res;
}

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 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 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 404 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Incorrect 1 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #2
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 760 KB Output is correct
4 Correct 3 ms 780 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 11 ms 8184 KB Output is correct
9 Correct 9 ms 8184 KB Output is correct
10 Correct 12 ms 8312 KB Output is correct
11 Correct 12 ms 8184 KB Output is correct
12 Correct 26 ms 16120 KB Output is correct
13 Correct 26 ms 16092 KB Output is correct
14 Correct 27 ms 15992 KB Output is correct
15 Correct 26 ms 15992 KB Output is correct
16 Correct 26 ms 15992 KB Output is correct
17 Correct 26 ms 16120 KB Output is correct
18 Correct 26 ms 16120 KB Output is correct
19 Correct 26 ms 16120 KB Output is correct
20 Correct 26 ms 16132 KB Output is correct
21 Incorrect 26 ms 16120 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 788 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 11 ms 8184 KB Output is correct
10 Correct 11 ms 8184 KB Output is correct
11 Correct 11 ms 8312 KB Output is correct
12 Correct 11 ms 8184 KB Output is correct
13 Correct 3 ms 8188 KB Output is correct
14 Correct 11 ms 8184 KB Output is correct
15 Correct 11 ms 8312 KB Output is correct
16 Correct 12 ms 8184 KB Output is correct
17 Correct 27 ms 16008 KB Output is correct
18 Correct 26 ms 15992 KB Output is correct
19 Correct 27 ms 16120 KB Output is correct
20 Correct 27 ms 16120 KB Output is correct
21 Correct 26 ms 16120 KB Output is correct
22 Correct 27 ms 16120 KB Output is correct
23 Correct 26 ms 15992 KB Output is correct
24 Correct 26 ms 16120 KB Output is correct
25 Correct 26 ms 16148 KB Output is correct
26 Correct 26 ms 15992 KB Output is correct
27 Correct 26 ms 15992 KB Output is correct
28 Correct 26 ms 15992 KB Output is correct
29 Correct 26 ms 16120 KB Output is correct
30 Correct 27 ms 16120 KB Output is correct
31 Correct 26 ms 16120 KB Output is correct
32 Correct 26 ms 16120 KB Output is correct
33 Correct 27 ms 15992 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16120 KB Output is correct
2 Correct 26 ms 16120 KB Output is correct
3 Correct 26 ms 16120 KB Output is correct
4 Correct 26 ms 16120 KB Output is correct
5 Correct 26 ms 16120 KB Output is correct
6 Correct 26 ms 15992 KB Output is correct
7 Correct 27 ms 16120 KB Output is correct
8 Correct 26 ms 16120 KB Output is correct
9 Incorrect 27 ms 15992 KB Output isn't correct
10 Halted 0 ms 0 KB -