Submission #934295
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<ll,int> P; const ll INF=1234567890123LL; int main() { int k,n; scanf(" %d %d", &k, &n); vector<P> b(n); rep(i,n) scanf(" %lld %d", &b[i].fi, &b[i].se); sort(all(b)); ll l=0, r=1234567890; while(r-l>1) { bool large=false; ll m=(l+r)/2; ll ct=0; rep(i,n) { //x回増築できる x<=(m-a_i)/d_i ll x = (m-b[i].fi)/b[i].se; if(x<0) x=0; ct+=x; if(x>k) { large=true; break; } } if(ct+n>k) large=true; if(large) r=m; else l=m; } // 全部lまで値段上げちゃっていい ll ans=0; ll ct=0; rep(i,n) { ll x = (l-b[i].fi)/b[i].se; if(x<0) x=0; ct+=x; ans+=x*b[i].fi; ans+=(x-1)*x/2*b[i].se; b[i].fi+=x*b[i].se; } priority_queue<P,vector<P>,greater<P>> pq; rep(i,n) pq.push(b[i]); while(ct<k) { P v=pq.top(); pq.pop(); ans+=v.fi; v.fi+=v.se; pq.push(v); ++ct; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 増築王高橋君 |
User | imulan |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 1568 Byte |
Status | AC |
Exec Time | 1189 ms |
Memory | 4640 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:19:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf(" %d %d", &k, &n); ^ ./Main.cpp:21:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] rep(i,n) scanf(" %lld %d", &b[i].fi, &b[i].se); ^
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 10 / 10 | 15 / 15 | 45 / 45 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample-01.txt, subtask0_sample-02.txt |
Subtask1 | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Subtask3 | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt |
Subtask4 | subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt, subtask4_01.txt, subtask4_02.txt, subtask4_03.txt, subtask4_04.txt, subtask4_05.txt, subtask4_06.txt, subtask4_07.txt, subtask4_08.txt, subtask4_09.txt, subtask4_10.txt, subtask4_11.txt, subtask4_12.txt, subtask4_13.txt, subtask4_14.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample-01.txt | AC | 21 ms | 1048 KB |
subtask0_sample-02.txt | AC | 18 ms | 916 KB |
subtask1_01.txt | AC | 20 ms | 924 KB |
subtask1_02.txt | AC | 19 ms | 920 KB |
subtask1_03.txt | AC | 20 ms | 1044 KB |
subtask1_04.txt | AC | 20 ms | 924 KB |
subtask1_05.txt | AC | 18 ms | 924 KB |
subtask1_06.txt | AC | 20 ms | 920 KB |
subtask1_07.txt | AC | 20 ms | 920 KB |
subtask1_08.txt | AC | 20 ms | 924 KB |
subtask1_09.txt | AC | 20 ms | 916 KB |
subtask1_10.txt | AC | 19 ms | 1044 KB |
subtask1_11.txt | AC | 19 ms | 924 KB |
subtask1_12.txt | AC | 20 ms | 920 KB |
subtask2_01.txt | AC | 20 ms | 924 KB |
subtask2_02.txt | AC | 20 ms | 1048 KB |
subtask2_03.txt | AC | 21 ms | 984 KB |
subtask2_04.txt | AC | 20 ms | 1044 KB |
subtask2_05.txt | AC | 18 ms | 920 KB |
subtask2_06.txt | AC | 23 ms | 1304 KB |
subtask2_07.txt | AC | 22 ms | 1044 KB |
subtask2_08.txt | AC | 21 ms | 1172 KB |
subtask2_09.txt | AC | 22 ms | 1172 KB |
subtask2_10.txt | AC | 23 ms | 1304 KB |
subtask2_11.txt | AC | 23 ms | 1168 KB |
subtask2_12.txt | AC | 22 ms | 1048 KB |
subtask3_01.txt | AC | 18 ms | 1044 KB |
subtask3_02.txt | AC | 20 ms | 1044 KB |
subtask3_03.txt | AC | 20 ms | 1048 KB |
subtask3_04.txt | AC | 64 ms | 4640 KB |
subtask3_05.txt | AC | 23 ms | 1300 KB |
subtask3_06.txt | AC | 22 ms | 1048 KB |
subtask3_07.txt | AC | 36 ms | 1892 KB |
subtask3_08.txt | AC | 75 ms | 4388 KB |
subtask3_09.txt | AC | 86 ms | 4576 KB |
subtask3_10.txt | AC | 79 ms | 4640 KB |
subtask3_11.txt | AC | 87 ms | 4636 KB |
subtask3_12.txt | AC | 58 ms | 2788 KB |
subtask4_01.txt | AC | 91 ms | 4576 KB |
subtask4_02.txt | AC | 21 ms | 848 KB |
subtask4_03.txt | AC | 23 ms | 1048 KB |
subtask4_04.txt | AC | 94 ms | 4624 KB |
subtask4_05.txt | AC | 20 ms | 1044 KB |
subtask4_06.txt | AC | 18 ms | 1048 KB |
subtask4_07.txt | AC | 1183 ms | 920 KB |
subtask4_08.txt | AC | 19 ms | 924 KB |
subtask4_09.txt | AC | 84 ms | 4284 KB |
subtask4_10.txt | AC | 19 ms | 912 KB |
subtask4_11.txt | AC | 102 ms | 4632 KB |
subtask4_12.txt | AC | 101 ms | 4632 KB |
subtask4_13.txt | AC | 100 ms | 4576 KB |
subtask4_14.txt | AC | 1189 ms | 1044 KB |