oj.uz

답안 #938577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938577 2024-03-05T10:24:37 Z danikoynov Two Dishes (JOI19_dishes) C++14
10 / 100
 10000 ms 34324 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10079 ms 26732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10079 ms 26732 KB Time limit exceeded
2 Halted 0 ms 0 KB -