oj.uz

Submission #955804

# Submission time Handle Problem Language Result Execution time Memory
955804 2024-03-31T12:37:06 Z vjudge1 Pinball (JOI14_pinball) C++17
29 / 100
 67 ms 235208 KB 
#include <bits/stdc++.h>

using namespace std;
vector<tuple<long long,long long,long long,long long> > v;
long long n,m;
bool visited[205][605][605];
long long dp[205][605][605];
map<long long,long long> prevod;
bool gotovo=false;
long long p=1;

long long f(long long poz,long long l,long long r)
{
    //cout<< "poz = "<<poz<<" l="<<l<<" r="<<r<<endl;
    if (poz==-1)
    {
        if (l==1 && r==prevod[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;

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

        v.push_back({a,b,c,d});
    }

    sort(pocetni.begin(),pocetni.end());
    for (long long i=0;i<pocetni.size();i++)
    {
        long long x=pocetni[i];
        if (prevod[x]==0)
        {
            prevod[x]=p;
            p++;
        }
    }
    if (prevod[n]==0) prevod[n]=p;

    for (long long i=0;i<v.size();i++)
    {
        get<0>(v[i])=prevod[get<0>(v[i])];
        get<1>(v[i])=prevod[get<1>(v[i])];
        get<2>(v[i])=prevod[get<2>(v[i])];
    }

    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 || pocetni[0]!=1) odg=-1;
    cout<<odg<<endl;
    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:55:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (long long i=0;i<pocetni.size();i++)
      |                        ~^~~~~~~~~~~~~~~
pinball.cpp:66:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (long long i=0;i<v.size();i++)
      |                        ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 67 ms 150412 KB Output is correct
10 Correct 40 ms 178144 KB Output is correct
11 Correct 43 ms 183380 KB Output is correct
12 Correct 57 ms 227832 KB Output is correct
13 Correct 59 ms 235208 KB Output is correct
14 Correct 62 ms 231508 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 67 ms 150412 KB Output is correct
10 Correct 40 ms 178144 KB Output is correct
11 Correct 43 ms 183380 KB Output is correct
12 Correct 57 ms 227832 KB Output is correct
13 Correct 59 ms 235208 KB Output is correct
14 Correct 62 ms 231508 KB Output is correct
15 Correct 17 ms 132932 KB Output is correct
16 Runtime error 13 ms 348 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16728 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 2 ms 16732 KB Output is correct
9 Correct 67 ms 150412 KB Output is correct
10 Correct 40 ms 178144 KB Output is correct
11 Correct 43 ms 183380 KB Output is correct
12 Correct 57 ms 227832 KB Output is correct
13 Correct 59 ms 235208 KB Output is correct
14 Correct 62 ms 231508 KB Output is correct
15 Correct 17 ms 132932 KB Output is correct
16 Runtime error 13 ms 348 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -