Submission #485687

#	Time	Username	Problem	Language	Result	Execution time	Memory
485687		Cross_Ratio	만두 (JOI14_ho_t2)	C++14	100 / 100	28 ms	668 KiB

2014_ho_t2

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int INF = 1e18;
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> A;
    int i, j, a, b;
    for(i=0;i<N;i++) {
        cin >> a;
        A.push_back(a);
    }
    sort(A.begin(),A.end(),[](int x, int y) {return x > y;});
    vector<P> B;
    for(i=0;i<M;i++) {
        cin >> a >> b;
        B.push_back(P(a,b));
    }
    vector<int> sA;
    sA.resize(N+1);
    for(i=1;i<=N;i++) {
        sA[i] = sA[i-1] + A[i-1];
    }
    vector<int> C;
    C.resize(N+1);
    fill(C.begin(),C.end(),INF);
    //cout << "C\n";
    C[0] = 0;
    for(j=0;j<M;j++) {
        for(i=N;i>=0;i--) {
            int k = min(N,i+B[j].first);
            C[k] = min(C[k], C[i] + B[j].second);
        }
    }
    int ans = 0;
    for(i=0;i<=N;i++) {
        ans = max(ans, sA[i] - C[i]);
    }
    cout << ans;
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40