Submission #1278008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278008		SabaKharebava	Festival (IOI25_festival)	C++20	0 / 100	1172 ms	2162688 KiB

festival

    #include<bits/stdc++.h>

    using namespace std;

    vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
        #define pb push_back
        int n = p.size();

        vector<vector<int>> f;
        for (int i = 0; i < n; i++) {
            f.pb({p[i], t[i], i});
        }

        sort(f.begin(), f.end(), [&](vector<int> a, vector<int> b) {
            if (a[1] == b[1])
                return a[0] < b[0];
            else {
                int A = -a[0]*a[1]*b[1] - b[0]*b[1];
                int B = -b[0]*a[1]*b[1] - a[0]*a[1];

                if (A == B)
                    return a[0] < b[0];
                return A > B;
            }
        });

        vector<int> ans;
        vector<vector<int>> dp(n+1, vector<int> (n+1, -1));
        // int dp[n+1][n+1]; // dp[i][j] -> choose j from first i
        // memset(dp, -1, sizeof dp);
        for (int i = 1; i <= n; i++) {
            dp[i][1] = (a-f[i-1][0]) * f[i-1][1];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j]);
                dp[i][j] = max((dp[i-1][j-1] - f[i-1][0]) * f[i-1][1], dp[i][j]);
            }
        }
        int am = n;
        while (am > 0 and dp[n][am] < 0) {
            am--;
        }
        if (am == 0)
            return {};

        int last = n;
        while (am > 0 and last > 0) {
            if (am == last or dp[last][am] != dp[last-1][am]) {
                ans.pb(f[last-1][2]);
                last--;
                am--;
                continue;
            }
            last--;
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }

    /*
    int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int n, a; cin>> n >> a;
        vector<int> p(n), t(n);

        for (int &e : p)
            cin>> e;
        for (int &e : t)
            cin>> e;

        vector<int> ans = max_coupons(a, p, t);
        for (int e : ans)
            cout<< e << ' ';
        cout<< '\n';
        return 0;
    }
    */

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18