oj.uz

Submission #731394

# Submission time Handle Problem Language Result Execution time Memory
731394 2023-04-27T11:44:04 Z alexdd Pinball (JOI14_pinball) C++17
29 / 100
 1000 ms 192256 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int b[100005];
int c[100005];
long long d[100005];
map<pair<int,int>,long long> dp[100005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    }
    for(int i=m;i>0;i--)
    {
        pair<int,int> cop;
        dp[i][{a[i],b[i]}] = d[i];
        for(auto it:dp[i+1])
        {
            if(it.second == 0)
                continue;
            cop = it.first;
            if(dp[i][cop] > it.second || dp[i][cop]==0)
                dp[i][cop] = it.second;
            if(cop.first <= c[i] && c[i]<=cop.second && (dp[i][{min(cop.first, a[i]),max(cop.second,b[i])}]==0 || dp[i][{min(cop.first, a[i]),max(cop.second,b[i])}] > it.second + d[i]))
                dp[i][{min(cop.first, a[i]),max(cop.second,b[i])}] = it.second + d[i];
        }
    }
    if(dp[1][{1,n}]==0)
        dp[1][{1,n}]=-1;
    cout<<dp[1][{1,n}];
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 23 ms 8532 KB Output is correct
10 Correct 64 ms 18124 KB Output is correct
11 Correct 97 ms 22948 KB Output is correct
12 Correct 101 ms 20812 KB Output is correct
13 Correct 164 ms 34076 KB Output is correct
14 Correct 436 ms 74376 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 23 ms 8532 KB Output is correct
10 Correct 64 ms 18124 KB Output is correct
11 Correct 97 ms 22948 KB Output is correct
12 Correct 101 ms 20812 KB Output is correct
13 Correct 164 ms 34076 KB Output is correct
14 Correct 436 ms 74376 KB Output is correct
15 Correct 7 ms 5972 KB Output is correct
16 Correct 743 ms 127320 KB Output is correct
17 Execution timed out 1081 ms 192256 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5028 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 5028 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 23 ms 8532 KB Output is correct
10 Correct 64 ms 18124 KB Output is correct
11 Correct 97 ms 22948 KB Output is correct
12 Correct 101 ms 20812 KB Output is correct
13 Correct 164 ms 34076 KB Output is correct
14 Correct 436 ms 74376 KB Output is correct
15 Correct 7 ms 5972 KB Output is correct
16 Correct 743 ms 127320 KB Output is correct
17 Execution timed out 1081 ms 192256 KB Time limit exceeded
18 Halted 0 ms 0 KB -