oj.uz

Submission #731324

# Submission time Handle Problem Language Result Execution time Memory
731324 2023-04-27T10:05:51 Z alexdd Pinball (JOI14_pinball) C++17
29 / 100
 1000 ms 194952 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int n,m;
int a[100005];
int b[100005];
int c[100005];
int d[100005];
map<pair<int,int>,int> 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 3 ms 4948 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 2 ms 4948 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 3 ms 4948 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 18 ms 8512 KB Output is correct
10 Correct 72 ms 18168 KB Output is correct
11 Correct 99 ms 22880 KB Output is correct
12 Correct 80 ms 20760 KB Output is correct
13 Correct 161 ms 34008 KB Output is correct
14 Correct 495 ms 74436 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 3 ms 4948 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 18 ms 8512 KB Output is correct
10 Correct 72 ms 18168 KB Output is correct
11 Correct 99 ms 22880 KB Output is correct
12 Correct 80 ms 20760 KB Output is correct
13 Correct 161 ms 34008 KB Output is correct
14 Correct 495 ms 74436 KB Output is correct
15 Correct 7 ms 6052 KB Output is correct
16 Correct 813 ms 127320 KB Output is correct
17 Execution timed out 1092 ms 194952 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 3 ms 4948 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 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 5024 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 18 ms 8512 KB Output is correct
10 Correct 72 ms 18168 KB Output is correct
11 Correct 99 ms 22880 KB Output is correct
12 Correct 80 ms 20760 KB Output is correct
13 Correct 161 ms 34008 KB Output is correct
14 Correct 495 ms 74436 KB Output is correct
15 Correct 7 ms 6052 KB Output is correct
16 Correct 813 ms 127320 KB Output is correct
17 Execution timed out 1092 ms 194952 KB Time limit exceeded
18 Halted 0 ms 0 KB -