Submission #938591

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938591	2024-03-05T10:51:27 Z	danikoynov	Two Dishes (JOI19_dishes)	C++14	10 / 100	10000 ms	30380 KB

dishes

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

int n, m;
ll a[maxn], s[maxn], p[maxn];
ll b[maxn], t[maxn], q[maxn];
ll pref[2][maxn];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> a[i] >> s[i] >> p[i];
    for (int i = 1; i <= m; i ++)
        cin >> b[i] >> t[i] >> q[i];
}

void prefix_sums()
{
    for (int i = 1; i <= n; i ++)
    {
        pref[0][i] = pref[0][i - 1] + a[i];
    }
    for (int i = 1; i <= m; i ++)
    {
        pref[1][i] = pref[1][i - 1] + b[i];
    }
}

ll dp[maxn], temp[maxn];
vector < pair < int, ll > > upd[maxn];
int X[maxn], Y[maxn];
const ll inf = 1e18;
void dynamic()
{
    for (int i = 1; i <= n; i ++)
    {
        ll free_time = s[i] - pref[0][i];
        while(X[i] <= m && pref[1][X[i]] <= free_time)
            X[i] ++;
        X[i] --;



        upd[i - 1].push_back({X[i] + 1, - p[i]});
        ///cout << "point " << i - 1 << " " << X[i] + 1 << " " << -p[i] << endl;


    }

    for (int i = 1; i <= m; i ++)
    {
        ll free_time = t[i] - pref[1][i];
        while(Y[i] <= n && pref[0][Y[i]] <= free_time)
            Y[i] ++;
        Y[i] --;

        if (Y[i] >= 0)
        {
            upd[Y[i]].push_back({i, q[i]});

            //cout << "point " << Y[i] << " " << i << " " << q[i] << endl;
        }
    }

    for (int j = 0; j <= m; j ++)
        dp[j] = 0;
    for (pair < int, ll > cur : upd[0])
        for (int d = cur.first; d <= m; d ++)
        dp[d] += cur.second;

    for (int i = 1; i <= n; i ++)
    {
        sort(upd[i].begin(), upd[i].end());
        for (int j = 0; j <= m; j ++)
            temp[j] = 0;
        for (pair < int, ll > cur : upd[i])
        {
            //cout << "update point " << cur.first << " " << cur.second << endl;

            for (int d = cur.first; d <= m; d ++)
            {
                temp[d] += cur.second;
            }
        }

        ll best = -inf;
        for (int j = 0; j <= m; j ++)
        {
            best = max(best, dp[j]);
            dp[j] = best + temp[j];
        }
        /**cout << "state " << i << endl;
        for (int j = 0; j <= m; j ++)
            cout << dp[j] << " ";
        cout << endl;*/
    }

    ll res = 0;
    for (int i = 1; i <= n; i ++)
        res += p[i];

    res = res + dp[m];
    cout << res << endl;




    /**for (int i = 0; i <= n; i ++)
    {
        for (int j = 0; j <= m; j ++)
        {
            if (i > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + (pref[0][i] + pref[1][j] <= s[i]));
            }
            if (j > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + (pref[0][i] + pref[1][j] <= t[j]));
            }

            ///cout << "state " << i << "  " << j << " " << dp[i][j] << endl;
        }
    }

    cout << dp[n][m] << endl;*/



}
void solve()
{
    input();
    prefix_sums();
    dynamic();
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
9 12
414814218 278771326 1
142790158 568604393 1
155567225 14012701 1
627555390 1224920860 1
677068511 5243031298 1
580933994 8598159379 1
819258172 1432469030 1
340548310 999347990 1
432162069 4373255579 1
99824657 11080715 1
756309567 9502204999 1
929699364 2343419815 1
376204577 6097684636 1
399553538 2306014840 1
824786328 4994974413 1
536419761 3247725215 1
953903194 10674273733 1
787043482 3936134684 1
105275489 567691865 1
861537554 117255456 1
434345770 2420939138 1

*/

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10042 ms	26608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16728 KB	Output is correct
4	Correct	3 ms	16816 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	4 ms	16868 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	2 ms	16728 KB	Output is correct
12	Correct	3 ms	16872 KB	Output is correct
13	Correct	3 ms	16984 KB	Output is correct
14	Correct	2 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16728 KB	Output is correct
4	Correct	3 ms	16816 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	4 ms	16868 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	2 ms	16728 KB	Output is correct
12	Correct	3 ms	16872 KB	Output is correct
13	Correct	3 ms	16984 KB	Output is correct
14	Correct	2 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	11 ms	16988 KB	Output is correct
18	Correct	12 ms	16988 KB	Output is correct
19	Correct	12 ms	16988 KB	Output is correct
20	Correct	11 ms	17032 KB	Output is correct
21	Correct	12 ms	17124 KB	Output is correct
22	Correct	12 ms	16988 KB	Output is correct
23	Correct	12 ms	16988 KB	Output is correct

Subtask #4
0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16728 KB	Output is correct
4	Correct	3 ms	16816 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	4 ms	16868 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	2 ms	16728 KB	Output is correct
12	Correct	3 ms	16872 KB	Output is correct
13	Correct	3 ms	16984 KB	Output is correct
14	Correct	2 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	11 ms	16988 KB	Output is correct
18	Correct	12 ms	16988 KB	Output is correct
19	Correct	12 ms	16988 KB	Output is correct
20	Correct	11 ms	17032 KB	Output is correct
21	Correct	12 ms	17124 KB	Output is correct
22	Correct	12 ms	16988 KB	Output is correct
23	Correct	12 ms	16988 KB	Output is correct
24	Execution timed out	10093 ms	30380 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16728 KB	Output is correct
4	Correct	3 ms	16816 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	4 ms	16868 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	2 ms	16728 KB	Output is correct
12	Correct	3 ms	16872 KB	Output is correct
13	Correct	3 ms	16984 KB	Output is correct
14	Correct	2 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	11 ms	16988 KB	Output is correct
18	Correct	12 ms	16988 KB	Output is correct
19	Correct	12 ms	16988 KB	Output is correct
20	Correct	11 ms	17032 KB	Output is correct
21	Correct	12 ms	17124 KB	Output is correct
22	Correct	12 ms	16988 KB	Output is correct
23	Correct	12 ms	16988 KB	Output is correct
24	Execution timed out	10093 ms	30380 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	16732 KB	Output is correct
2	Correct	3 ms	16732 KB	Output is correct
3	Correct	3 ms	16728 KB	Output is correct
4	Correct	3 ms	16816 KB	Output is correct
5	Correct	3 ms	16732 KB	Output is correct
6	Correct	4 ms	16868 KB	Output is correct
7	Correct	3 ms	16732 KB	Output is correct
8	Correct	2 ms	16732 KB	Output is correct
9	Correct	3 ms	16732 KB	Output is correct
10	Correct	3 ms	16732 KB	Output is correct
11	Correct	2 ms	16728 KB	Output is correct
12	Correct	3 ms	16872 KB	Output is correct
13	Correct	3 ms	16984 KB	Output is correct
14	Correct	2 ms	16732 KB	Output is correct
15	Correct	3 ms	16732 KB	Output is correct
16	Correct	3 ms	16732 KB	Output is correct
17	Correct	11 ms	16988 KB	Output is correct
18	Correct	12 ms	16988 KB	Output is correct
19	Correct	12 ms	16988 KB	Output is correct
20	Correct	11 ms	17032 KB	Output is correct
21	Correct	12 ms	17124 KB	Output is correct
22	Correct	12 ms	16988 KB	Output is correct
23	Correct	12 ms	16988 KB	Output is correct
24	Execution timed out	10093 ms	30380 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10042 ms	26608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	10042 ms	26608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #938591

Compilation message