Submission #1217757
Source Code Expand
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<stack> #include<queue> #include<vector> #include<algorithm> #include<iomanip> typedef long long int ll; using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define REP(i,n) for (int i=0;i<(n);i++) #define EREP(i,n) for (int i=1;i<=(n);i++) #define ALL(a) (a).begin(),(a).end() //#define EVEL 1 #ifndef EVEL #define DEB(X) cout << #X << ":" <<X<<" " ; #define TF(f) f ? cout<<"true " : cout<<"false "; #define END cout<<"\n"; #else #define DEB(X) {X=X;} #define TF(f) {f=f;} #define END {} #endif const int MOD = 1000000007; const ll INF = 10000000000000; #define NMAX 50 #define MAX 10 int N, K; int A[20]; int nh; ll ans = 0; int binary(int bina) { int ans = 0; for (int i = 0; bina>0; i++) { ans = ans + (bina % 2)*pow(10, i); bina = bina / 2; } return ans; } int_fast8_t popcount(uint32_t bits) { #ifdef __GNUC__ return __builtin_popcount(bits); #endif bits = bits - (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = bits + (bits >> 4) & 0x0f0f0f0f; bits = bits * 0x01010101; return bits >> 24; } int main() { cin >> N >> K; REP(i, N)cin >> A[i]; ans = INF; REP(bit, (1 << N)) { if (popcount(bit)<K) { continue; } ll count = 0, front = A[0]; //cout<<binary(bit)<<endl; REP(i, N) { if (i == 0) { continue; } if ((bit >> i) & 1) { if (front<A[i]) { front = A[i]; } else { front++; count += front - A[i]; } } else { if (front<A[i]) { count = INF; break; } } } ans = min(ans, count); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Buildings are Colorful! |
User | eiya |
Language | C++14 (GCC 5.4.1) |
Score | 350 |
Code Size | 1713 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 120 / 120 | 90 / 90 | 140 / 140 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sub0_in1.txt, sub0_in2.txt |
Subtask1 | sub1_in1.txt, sub1_in2.txt |
Subtask2 | sub2_in1.txt, sub2_in2.txt, sub2_in3.txt |
Subtask3 | sub0_in1.txt, sub0_in2.txt, sub1_in1.txt, sub1_in2.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub3_in1.txt, sub3_in2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sub0_in1.txt | AC | 1 ms | 256 KB |
sub0_in2.txt | AC | 1 ms | 256 KB |
sub1_in1.txt | AC | 1 ms | 256 KB |
sub1_in2.txt | AC | 1 ms | 256 KB |
sub2_in1.txt | AC | 1 ms | 256 KB |
sub2_in2.txt | AC | 1 ms | 256 KB |
sub2_in3.txt | AC | 1 ms | 256 KB |
sub3_in1.txt | AC | 1 ms | 256 KB |
sub3_in2.txt | AC | 1 ms | 256 KB |