oj.uz

Submission #41146

# Submission time Handle Problem Language Result Execution time Memory
41146 2018-02-13T06:01:24 Z prateep Stove (JOI18_stove) C++11
100 / 100
 34 ms 2144 KB 
#pragma comment(linker,"/STACK:36777216")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <iterator>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <cassert>
#include <deque>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <ctime>
#include <climits>
#include <stdexcept>
#include <cfloat>

using namespace std;

#define LET(x,a)        ::typeid(a) x(a)
#define IFOR(i,a,b)     for(LET(i,a);i!=(b);++i)
#define EACH(it,v)      IFOR(it,v.begin(),v.end())
#define FOR(i,a,b)      for(int i = (a); i < int(b);i++)
#define REP(i,n)        FOR(i,0,n)
#define SZ              size()
#define PB              push_back
#define PF              push_front
#define V(x)            vector< x >
#define two(X)          (1<<(X))
#define twoL(X)         (((int64)(1))<<(X))
#define contain(S,X)    (((S)&two(X))!=0)
#define containL(S,X)   (((S)&twoL(X))!=0
#define swap(x,y)       x ^=y ^= x^=y
#define ALL(v)          (v).begin(),(v).end()
#define DBN1(a)         cerr<<#a<<"="<<(a)<<"\n"

const double pi = acos(-1.0);
const double eps = 1e-11;
const int oo = 0x3f3f3f3f;
template<class T> inline void checkmin(T &a, T b){ if (b<a) a = b; }
template<class T> inline void checkmax(T &a, T b){ if (b>a) a = b; }
template<class T> inline T sqr(T x){ return x*x; }
typedef pair<int, int> ipair;
template<class T> inline T lowbit(T n){ return (n ^ (n - 1))&n; }
template<class T> inline int countbit(T n){ return (n == 0) ? 0 : (1 + countbit(n&(n - 1))); }
template<class T> inline T gcd(T a, T b) { T c; while (a != 0) { c = a; a = b%a;  b = c; } return b; }
template<class T> inline T mabs(T a) { if (a < 0) return -a; else return a; }

typedef V(int)          VI;
typedef V(VI)           VII;
typedef V(string)       VS;
typedef long long       int64;
typedef long double     LD;
typedef pair<int, int>   PI;
typedef pair<double, double> PD;

const int N = (int) 1e5+111;
const int MOD = (int) 1e9+7;
int64 a[N], d[N];
inline int solve(int testnum)
{
    int n,k; scanf("%d%d",&n,&k);
	REP(i,n) {
		scanf("%lld",&a[i]);
		if(i > 0) d[i] = a[i] - a[i-1];
		else d[0] = oo;
	}
	int64 big = a[n-1] - a[0] + k;
	sort(d+1,d+n,greater<int64>());
	for(int i = 1; i <= min(k-1, n-1); i++) {
		big -= d[i];
	}
	printf("%lld\n", big);
	return 0;
}

int main(int argc, char* argv[])
{
#ifdef LocalHost
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	int t = 1; //scanf("%d", &t);
	if (argc > 1) t = atoi(argv[1]);
	FOR(_t, 1, t + 1) {
		int ret = ::solve(_t);
		if (ret == -1) {
	         // cerr << "Failed test #" << _t << endl;
        	  break;
		}
		//cerr << "Solved test #" << _t << endl;
	}
#ifdef LocalHost
	printf("Time taken : %.10f seconds\n", (1.0f*clock()) / CLOCKS_PER_SEC);
#endif
	return 0;
}

Compilation message

stove.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker,"/STACK:36777216")
 ^
stove.cpp: In function 'int solve(int)':
stove.cpp:78:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n,k; scanf("%d%d",&n,&k);
                                 ^
stove.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 1 ms 484 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 528 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 2 ms 528 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 3 ms 660 KB Output is correct
15 Correct 2 ms 660 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 1 ms 484 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 528 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 2 ms 528 KB Output is correct
8 Correct 1 ms 532 KB Output is correct
9 Correct 2 ms 532 KB Output is correct
10 Correct 2 ms 532 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 3 ms 660 KB Output is correct
15 Correct 2 ms 660 KB Output is correct
16 Correct 33 ms 2144 KB Output is correct
17 Correct 27 ms 2144 KB Output is correct
18 Correct 30 ms 2144 KB Output is correct
19 Correct 26 ms 2144 KB Output is correct
20 Correct 26 ms 2144 KB Output is correct
21 Correct 26 ms 2144 KB Output is correct
22 Correct 26 ms 2144 KB Output is correct
23 Correct 27 ms 2144 KB Output is correct
24 Correct 34 ms 2144 KB Output is correct