oj.uz

답안 #955773

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955773 2024-03-31T12:04:46 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 1000 ms 169356 KB 
#include <bits/stdc++.h>

using namespace std;
vector<tuple<long long,long long,long long,long long> > v;
long long n,m;
map<tuple<long long,long long,long long>,bool> visited;
map<tuple<long long,long long,long long>,long long> dp;
bool gotovo=false;

long long f(long long poz,long long l,long long r)
{
    if (poz==-1)
    {
        if (l==1 && r==n)
        {
            gotovo=true;
            return 0;
        }
        return 1000000000000000;
    }
    if (visited[{poz,l,r}]) return dp[{poz,l,r}];

    long long op1=f(poz-1,l,r);
    long long op2=1000000000000000;

    long long a=get<0>(v[poz]),b=get<1>(v[poz]),c=get<2>(v[poz]);
    if (c>=l && c<=r) op2=f(poz-1,min(a,l),max(b,r))+get<3>(v[poz]);

    long long odg=min(op1,op2);
    visited[{poz,l,r}]=true;
    dp[{poz,l,r}]=odg;
    return odg;
}

int main()
{
    cin>>m>>n;

    for (long long i=0;i<m;i++)
    {
        long long a,b,c,d;
        cin>>a>>b>>c>>d;
        v.push_back({a,b,c,d});
    }

    long long odg=1000000000000000;
    for (long long i=m-1;i>=0;i--)
        odg = min(odg,get<3>(v[i])+f(i-1,get<0>(v[i]),get<1>(v[i])));

    if (gotovo==false) odg=-1;
    cout<<odg<<endl;
    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 33 ms 9052 KB Output is correct
10 Correct 168 ms 32720 KB Output is correct
11 Correct 247 ms 44696 KB Output is correct
12 Correct 175 ms 38968 KB Output is correct
13 Correct 403 ms 71740 KB Output is correct
14 Execution timed out 1053 ms 169356 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 33 ms 9052 KB Output is correct
10 Correct 168 ms 32720 KB Output is correct
11 Correct 247 ms 44696 KB Output is correct
12 Correct 175 ms 38968 KB Output is correct
13 Correct 403 ms 71740 KB Output is correct
14 Execution timed out 1053 ms 169356 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 33 ms 9052 KB Output is correct
10 Correct 168 ms 32720 KB Output is correct
11 Correct 247 ms 44696 KB Output is correct
12 Correct 175 ms 38968 KB Output is correct
13 Correct 403 ms 71740 KB Output is correct
14 Execution timed out 1053 ms 169356 KB Time limit exceeded
15 Halted 0 ms 0 KB -