Submission #543864

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543864	2022-03-31T14:04:50 Z	ala2	Go (COCI18_go)	C++14	40 / 100	1000 ms	320208 KB

go

#include <bits/stdc++.h>
#define int long long
//#define first first
//#define second second
#define pb push_back
#define B begin()
#define E end()
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
vector < pair< int ,pair<int,int>  >  >v;
const int inf=1e18;
int n,k;
int dp[101][101][2002][2];
int d(int i,int j)
{
//    cout<<"       :::     "<<i<< "   "<<j<<"   "<<fabs( v[i].first-v[j].first )<<endl;
    return  fabs( v[i].first-v[j].first );
}
int f(int l,int r,int t,int bo)
{

    if(l==0&&r==n-1)
        return 0;
    if(t>2000)
        return 0;
    if(l<0)
        return -inf;
    if(r>=n||l>=n)
        //return -inf;            cout<<"                           "<<n<<"    "<<r<<endl;

    if(dp[l][r][t][bo]!=-1)
        return dp[l][r][t][bo];
    if(bo==0)
    {

        int one=f(l-1,r,t+d(l-1,l),0)+( (t+d(l-1,l)<v[l-1].second.second)*v[l-1].second.first );
        int tow=0;
        if(r<n-1) tow=f(l,r+1,t+d(l,r+1),1)+( (t+d(l,r+1)<v[r+1].second.second)*v[r+1].second.first );
        return dp[l][r][t][bo]=max(one,tow);
    }
    if(bo==1)
    {
        int one=f(l-1,r,t+d(l-1,r),0)+( (t+d(l-1,r)<v[l-1].second.second)*v[l-1].second.first );
        int tow=0;
        if(r<n-1) tow=f(l,r+1,t+d(r,r+1),1)+( (t+d(r,r+1)<v[r+1].second.second)*v[r+1].second.first );
        return dp[l][r][t][bo]=max(one,tow);
    }

}
signed main()
{
    //int n,k;
    FAST
    memset(dp,-1,sizeof dp);
    map<int,int>m;
    cin>>n>>k>>n;
    for(int i=0;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        m[x]=1;
        v.pb( {x,{y,z}} );
    }
    if(m[k]==0)
    {
        v.pb( {k,{0,1}} );
        n++;
    }

    sort(v.B,v.E);
    for(int i=0;i<n;i++)
    {
        if(v[i].first==k)
        {
            cout<<f(i,i,0,0)<<endl;
        }
    }





}

//111

Compilation message

go.cpp: In function 'long long int f(long long int, long long int, long long int, long long int)':
go.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	319948 KB	Output is correct
2	Correct	114 ms	319916 KB	Output is correct
3	Correct	133 ms	319932 KB	Output is correct
4	Correct	128 ms	319980 KB	Output is correct
5	Execution timed out	1106 ms	320020 KB	Time limit exceeded
6	Execution timed out	1099 ms	320208 KB	Time limit exceeded
7	Execution timed out	1110 ms	319904 KB	Time limit exceeded
8	Execution timed out	1104 ms	319936 KB	Time limit exceeded
9	Execution timed out	1111 ms	320036 KB	Time limit exceeded
10	Execution timed out	1100 ms	319948 KB	Time limit exceeded