oj.uz

Submission #203291

# Submission time Handle Problem Language Result Execution time Memory
203291 2020-02-20T06:48:01 Z wendy_virgo Stove (JOI18_stove) C++14
100 / 100
 112 ms 165096 KB 
#include <bits/stdc++.h>

using namespace std;

#define taskname "JOI18_stove"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front

template<typename TH>
void _dbg(const char* sdbg, TH h)
{
	cerr << sdbg << " = " << h << "\n";
}

template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
	while (*sdbg != ',') cerr << *sdbg++;
	cerr << " = " << h << ",";
	_dbg(sdbg + 1, t...);
}

#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";

const int N=1e5+5;
const int64_t LINF=1e18;

int n,k;
int64_t a[N],f[5005][5005],g[5005][5005];

void Sub2()
{
    forinc(i,0,n)
    {
        forinc(j,0,k)
        {
            f[i][j]=LINF;
            g[i][j]=LINF;
        }
    }
    f[0][0]=0;
    // g[i][j] = min(f[0<=x<=i][j]-a[x+1])
    forinc(i,0,n)
    {
        g[i][0]=-a[1];
    }
    forinc(i,1,n)
    {
        forinc(j,1,k)
        {
//            forinc(p,0,i-1)
//            {
//                if(f[p][j-1]!=LINF)
//                {
//                    f[i][j]=min(f[i][j],f[p][j-1]+(a[i]-a[p+1]+1));
//                }
//            }
            if(g[i-1][j-1]!=LINF)
            {
                f[i][j]=g[i-1][j-1]+a[i]+1;
                g[i][j]=min(g[i-1][j],f[i][j]-a[i+1]);
            }
        }
    }
    int64_t ans=LINF;
    forinc(i,0,k)
    {
        ans=min(ans,f[n][i]);
    }
    cout<<ans<<'\n';
}

void Sub3()
{
    vector<int> vec;
    forinc(i,1,n-1)
    {
        vec.pb(a[i]-a[i+1]);
    }
    sort(all(vec));
    int ans=k-a[1]+a[n];
    forinc(i,0,k-2)
    {
        ans+=vec[i];
    }
    cout<<ans;
}

int64_t Random(int64_t l,int64_t r)
{
    int64_t f1=RAND_MAX+1;
    int64_t f2=f1*f1;
    int64_t f3=f1*f1*f1;
    return l+((int64_t)rand()*f3+(int64_t)rand()*f2+(int64_t)rand()*f1+(int64_t)rand())%(r-l+1);
}

void Gen()
{
    srand(time(0));
    freopen("JOI18_stove.INP","w",stdout);
    int n=Random(1,10);
    int k=Random(1,n);
    cout<<n<<' '<<k<<'\n';
    int x=Random(1,10);
    cout<<x<<' ';
    forinc(i,2,n)
    {
        int64_t y=x+1+Random(1,1e5);
        cout<<y<<' ';
        x=y;
    }
    exit(0);
}

int main()
{
//    Gen();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
//	freopen(taskname".INP","r",stdin);
	#endif // ONLINE_JUDGE
	cin>>n>>k;
	forinc(i,1,n)
	{
	    cin>>a[i];
	}
	if(n<=5e3)
    {
        Sub2();
    }
    else
    {
        Sub3();
    }
    return 0;
}

Compilation message

stove.cpp: In function 'int64_t Random(int64_t, int64_t)':
stove.cpp:101:24: warning: integer overflow in expression [-Woverflow]
     int64_t f1=RAND_MAX+1;
                        ^
stove.cpp: In function 'void Gen()':
stove.cpp:110:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("JOI18_stove.INP","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 18 ms 25336 KB Output is correct
11 Correct 21 ms 29564 KB Output is correct
12 Correct 48 ms 71800 KB Output is correct
13 Correct 75 ms 118648 KB Output is correct
14 Correct 112 ms 160888 KB Output is correct
15 Correct 107 ms 165096 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 18 ms 25336 KB Output is correct
11 Correct 21 ms 29564 KB Output is correct
12 Correct 48 ms 71800 KB Output is correct
13 Correct 75 ms 118648 KB Output is correct
14 Correct 112 ms 160888 KB Output is correct
15 Correct 107 ms 165096 KB Output is correct
16 Correct 36 ms 2808 KB Output is correct
17 Correct 29 ms 2676 KB Output is correct
18 Correct 28 ms 2680 KB Output is correct
19 Correct 28 ms 2680 KB Output is correct
20 Correct 30 ms 2680 KB Output is correct
21 Correct 28 ms 2680 KB Output is correct
22 Correct 29 ms 2680 KB Output is correct
23 Correct 29 ms 2680 KB Output is correct
24 Correct 29 ms 2680 KB Output is correct