Submission #344289

#	Time	Username	Problem	Language	Result	Execution time	Memory
344289		aryanc403	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	875 ms	500 KiB

bulves

/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#ifdef ARYANC403
    #include "/home/aryan/codes/PastCodes/template/header.h"
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    #pragma GCC optimize ("-ffloat-store")
    #include<iostream>
    #include<bits/stdc++.h>
    #define dbg(args...)
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;


const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{

    cin>>n;
    a.pb(0);
    fo(i,n)
    {
        cin>>l>>r;
        a.pb(l-r);
    }

    const lli N=100;
    vi dp(2*N+1,INF);
    dp[N]=0;
    dbg(a);
    for(lli i=1;i<=n;++i)
    {
        if(a[i]==0)
            continue;
        vi cur(2*N+1,INF);
        if(a[i]<0)
        {
            const lli x=-a[i];
            for(lli j=-N;j<=0;++j)
            {
                if(j-x<-N||j-x>N)
                    continue;
                cur[j-x+N]=min(cur[j-x+N],dp[j+N]-x*i);
            }
            for(lli j=0;j<=N;++j)
            {
                if(j-x<-N||j-x>N)
                    continue;
                if(j<=x)
                    cur[j-x+N]=min(cur[j-x+N],dp[j+N]+2*j*i-x*i);
                else
                    cur[j-x+N]=min(cur[j-x+N],dp[j+N]+x*i);
            }
        }
        else
        {
            // const lli x=a[i];
            for(lli x=0;x<=a[i];++x)
            {
                for(lli j=0;j<=N;++j)
                {
                    if(j+x<-N||j+x>N)
                        continue;
                    cur[j+x+N]=min(cur[j+x+N],dp[j+N]-x*i);
                }
                for(lli j=-N;j<=0;++j)
                {
                    if(j+x<-N||j+x>N)
                        continue;
                    if(j>=-x)
                        cur[j+x+N]=min(cur[j+x+N],dp[j+N]-2*j*i-x*i);
                    else
                        cur[j+x+N]=min(cur[j+x+N],dp[j+N]+x*i);
                }
            }
        }
        cur.swap(dp);
        // dbg(dp);
        dbg(dp[N-2],dp[N-1],dp[N],dp[N+1],dp[N+2],dp[N+3]);
    }
    cout<<dp[N]<<endl;
}   aryanc403();
    return 0;
}

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36