oj.uz

Submission #95420

# Submission time Handle Problem Language Result Execution time Memory
95420 2019-02-01T04:06:15 Z easrui None (JOI14_ho_t2) C++14
0 / 100
 152 ms 1320 KB 
#include <bits/stdc++.h>
using namespace std;
const int MM = 1e4+5;
const int MN = 505;
int M,N,P[MM],S[MM],C[MN],E[MN],ans,res;
int D[10*MM][2];

int main()
{
    //freopen("input.txt","r",stdin);
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> M >> N;
    for(int i=1; i<=M; i++)
        cin >> P[i];
    sort(P+1,P+M+1,greater<int>());
    for(int i=1; i<=M; i++){
        S[i] = S[i-1] + P[i];
    }
    for(int i=1; i<=1e5; i++) D[i][0] = D[i][1] = 1e9;
    for(int i=1; i<=N; i++) cin >> C[i] >> E[i];
    for(int i=1; i<=N; i++){
        for(int j=1e5; j>=0; j--){
            if(j>=C[i]) D[j][i%2] = min(D[j][(i+1)%2],D[j-C[i]][(i+1)%2] + E[i]);
            if(j!=1e5) D[j][i%2] = min(D[j][i%2],D[j+1][i%2]);
        }
    }
    //cout << D[2][N%2];
    for(int i=0; i<=M; i++){
        ans = max(ans,S[i]-D[i][N%2]);
    }
    cout << ans;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 7 ms 1144 KB Output is correct
3 Correct 7 ms 1320 KB Output is correct
4 Correct 6 ms 1288 KB Output is correct
5 Correct 6 ms 1272 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 6 ms 1144 KB Output is correct
8 Correct 5 ms 1144 KB Output is correct
9 Incorrect 7 ms 1272 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1248 KB Output is correct
2 Correct 147 ms 1144 KB Output is correct
3 Correct 150 ms 1248 KB Output is correct
4 Correct 145 ms 1248 KB Output is correct
5 Correct 152 ms 1144 KB Output is correct
6 Incorrect 140 ms 1272 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 7 ms 1144 KB Output is correct
3 Correct 7 ms 1320 KB Output is correct
4 Correct 6 ms 1288 KB Output is correct
5 Correct 6 ms 1272 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 6 ms 1144 KB Output is correct
8 Correct 5 ms 1144 KB Output is correct
9 Incorrect 7 ms 1272 KB Output isn't correct
10 Halted 0 ms 0 KB -