Submission #138022
Source Code Expand
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<complex>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define sz(x) (int)(x).size()
#define popcount __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
const int MX = 100005, INF = 1000000005;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
const int dx[] = {-1,0,1,0}, dy[] = {0,-1,0,1}; //<^>v
int n, m, k;
P p[MX];
bool f(int c){
int x = 0, h = 0, pi = 0, last = 0;
priority_queue<int> q;
while(x+c <= m){
while(pi < n && p[pi].fi <= x+c){
q.push(-p[pi++].se);
}
if(q.size()){
int nx = -q.top(); q.pop();
last = max(last,nx);
if(nx > x){
x = min(x+c,nx);
}
} else {
if(x == last) return false;
x = last;
h++;
}
}
return (h <= k);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
rep(i,n) scanf("%d%d",&p[i].fi,&p[i].se);
sort(p,p+n);
int l = 0, r = INF, c;
while(l+1<r){
c = l+r>>1;
if(f(c)) r = c; else l = c;
}
cout << r << endl;
return 0;
}
Submission Info
Submission Time
2014-03-02 14:48:46+0900
Task
G - 夏休みの掃除当番
User
snuke
Language
C++ (G++ 4.6.4)
Score
200
Code Size
1794 Byte
Status
AC
Exec Time
553 ms
Memory
2488 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:68:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:70:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name
Small
Large
Score / Max Score
50 / 50
150 / 150
Status
Set Name
Test Cases
Small
sample01, small-hand00, small-hand01, small-random00, small-random01, small-random02, small-random03, small-random04, small-random05, small-random06, small-random07, small-random08, small-random09, small-random10, small-random11
Large
sample02, sample03, large-hand00, large-hand01, large-hand02, large-hand03, large-hand04, large-random00, large-random01, large-random02, large-random03, large-random04, large-random05, large-random06, large-random07, large-random08, large-random09, large-random10, large-random11, large-random12, large-random13, large-random14, small-hand00, small-hand01, small-random00, small-random01, small-random02, small-random03, small-random04, small-random05, small-random06, small-random07, small-random08, small-random09, small-random10, small-random11
Case Name
Status
Exec Time
Memory
large-hand00
AC
23 ms
1564 KB
large-hand01
AC
22 ms
1692 KB
large-hand02
AC
159 ms
1960 KB
large-hand03
AC
169 ms
2216 KB
large-hand04
AC
150 ms
2156 KB
large-random00
AC
432 ms
2392 KB
large-random01
AC
435 ms
2436 KB
large-random02
AC
422 ms
2488 KB
large-random03
AC
372 ms
2328 KB
large-random04
AC
438 ms
2480 KB
large-random05
AC
460 ms
2444 KB
large-random06
AC
358 ms
2356 KB
large-random07
AC
502 ms
2436 KB
large-random08
AC
494 ms
2356 KB
large-random09
AC
480 ms
2352 KB
large-random10
AC
468 ms
2364 KB
large-random11
AC
402 ms
2256 KB
large-random12
AC
553 ms
2408 KB
large-random13
AC
441 ms
2364 KB
large-random14
AC
422 ms
2396 KB
sample01
AC
23 ms
1576 KB
sample02
AC
25 ms
1696 KB
sample03
AC
22 ms
1688 KB
small-hand00
AC
21 ms
1692 KB
small-hand01
AC
158 ms
2216 KB
small-random00
AC
375 ms
2364 KB
small-random01
AC
330 ms
2368 KB
small-random02
AC
373 ms
2368 KB
small-random03
AC
430 ms
2332 KB
small-random04
AC
424 ms
2384 KB
small-random05
AC
432 ms
2328 KB
small-random06
AC
484 ms
2348 KB
small-random07
AC
490 ms
2348 KB
small-random08
AC
481 ms
2356 KB
small-random09
AC
538 ms
2428 KB
small-random10
AC
546 ms
2300 KB
small-random11
AC
545 ms
2260 KB