Submission #938577

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
938577	2024-03-05T10:24:37 Z	danikoynov	Two Dishes (JOI19_dishes)	C++14	10 / 100	10000 ms	34324 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];
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 (int i = 1; i <= n; i ++)
    {
        sort(upd[i].begin(), upd[i].end());
        for (pair < int, ll > cur : upd[i - 1])
        {
            //cout << "update point " << cur.first << " " << cur.second << endl;
            for (int d = cur.first; d <= m; d ++)
            {
                dp[d] += cur.second;
            }
        }

        for (int j = 1; j <= m; j ++)
        {
            dp[j] = max(dp[j], dp[j - 1]);
        }
        /**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];
    for (pair < int, ll > cur : upd[n])
    {
        if (cur.first <= m)
        res += cur.second;
    }

    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	10079 ms	26732 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	3 ms	14684 KB	Output is correct
4	Correct	3 ms	14904 KB	Output is correct
5	Correct	3 ms	14684 KB	Output is correct
6	Correct	2 ms	14680 KB	Output is correct
7	Correct	2 ms	14684 KB	Output is correct
8	Correct	2 ms	14684 KB	Output is correct
9	Correct	2 ms	14936 KB	Output is correct
10	Correct	2 ms	14816 KB	Output is correct
11	Correct	3 ms	14684 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14684 KB	Output is correct
15	Correct	2 ms	14684 KB	Output is correct
16	Correct	3 ms	14684 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	3 ms	14684 KB	Output is correct
4	Correct	3 ms	14904 KB	Output is correct
5	Correct	3 ms	14684 KB	Output is correct
6	Correct	2 ms	14680 KB	Output is correct
7	Correct	2 ms	14684 KB	Output is correct
8	Correct	2 ms	14684 KB	Output is correct
9	Correct	2 ms	14936 KB	Output is correct
10	Correct	2 ms	14816 KB	Output is correct
11	Correct	3 ms	14684 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14684 KB	Output is correct
15	Correct	2 ms	14684 KB	Output is correct
16	Correct	3 ms	14684 KB	Output is correct
17	Correct	10 ms	15196 KB	Output is correct
18	Correct	11 ms	15136 KB	Output is correct
19	Correct	12 ms	15136 KB	Output is correct
20	Correct	10 ms	15196 KB	Output is correct
21	Correct	11 ms	15084 KB	Output is correct
22	Correct	11 ms	14940 KB	Output is correct
23	Correct	11 ms	14940 KB	Output is correct

Subtask #4
0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	3 ms	14684 KB	Output is correct
4	Correct	3 ms	14904 KB	Output is correct
5	Correct	3 ms	14684 KB	Output is correct
6	Correct	2 ms	14680 KB	Output is correct
7	Correct	2 ms	14684 KB	Output is correct
8	Correct	2 ms	14684 KB	Output is correct
9	Correct	2 ms	14936 KB	Output is correct
10	Correct	2 ms	14816 KB	Output is correct
11	Correct	3 ms	14684 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14684 KB	Output is correct
15	Correct	2 ms	14684 KB	Output is correct
16	Correct	3 ms	14684 KB	Output is correct
17	Correct	10 ms	15196 KB	Output is correct
18	Correct	11 ms	15136 KB	Output is correct
19	Correct	12 ms	15136 KB	Output is correct
20	Correct	10 ms	15196 KB	Output is correct
21	Correct	11 ms	15084 KB	Output is correct
22	Correct	11 ms	14940 KB	Output is correct
23	Correct	11 ms	14940 KB	Output is correct
24	Execution timed out	10006 ms	34324 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	3 ms	14684 KB	Output is correct
4	Correct	3 ms	14904 KB	Output is correct
5	Correct	3 ms	14684 KB	Output is correct
6	Correct	2 ms	14680 KB	Output is correct
7	Correct	2 ms	14684 KB	Output is correct
8	Correct	2 ms	14684 KB	Output is correct
9	Correct	2 ms	14936 KB	Output is correct
10	Correct	2 ms	14816 KB	Output is correct
11	Correct	3 ms	14684 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14684 KB	Output is correct
15	Correct	2 ms	14684 KB	Output is correct
16	Correct	3 ms	14684 KB	Output is correct
17	Correct	10 ms	15196 KB	Output is correct
18	Correct	11 ms	15136 KB	Output is correct
19	Correct	12 ms	15136 KB	Output is correct
20	Correct	10 ms	15196 KB	Output is correct
21	Correct	11 ms	15084 KB	Output is correct
22	Correct	11 ms	14940 KB	Output is correct
23	Correct	11 ms	14940 KB	Output is correct
24	Execution timed out	10006 ms	34324 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	14684 KB	Output is correct
2	Correct	2 ms	14684 KB	Output is correct
3	Correct	3 ms	14684 KB	Output is correct
4	Correct	3 ms	14904 KB	Output is correct
5	Correct	3 ms	14684 KB	Output is correct
6	Correct	2 ms	14680 KB	Output is correct
7	Correct	2 ms	14684 KB	Output is correct
8	Correct	2 ms	14684 KB	Output is correct
9	Correct	2 ms	14936 KB	Output is correct
10	Correct	2 ms	14816 KB	Output is correct
11	Correct	3 ms	14684 KB	Output is correct
12	Correct	3 ms	14940 KB	Output is correct
13	Correct	3 ms	14940 KB	Output is correct
14	Correct	3 ms	14684 KB	Output is correct
15	Correct	2 ms	14684 KB	Output is correct
16	Correct	3 ms	14684 KB	Output is correct
17	Correct	10 ms	15196 KB	Output is correct
18	Correct	11 ms	15136 KB	Output is correct
19	Correct	12 ms	15136 KB	Output is correct
20	Correct	10 ms	15196 KB	Output is correct
21	Correct	11 ms	15084 KB	Output is correct
22	Correct	11 ms	14940 KB	Output is correct
23	Correct	11 ms	14940 KB	Output is correct
24	Execution timed out	10006 ms	34324 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	10079 ms	26732 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	10079 ms	26732 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Submission #938577

Compilation message