Submission #1698660


Source Code Expand

#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; ++i)
#define FOR(i,n,m) for(long long i=n; i<m; ++i)
#define DUMP(n,a) for(long long dump=0; dump<n; ++dump) { cout<<a[dump]; if(dump!=n-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int c1=0,c2=0,c3=0,c4=0;
	int n;
	cin>>n;
	REP(i,n) {
		int a;
		cin>>a;
		if(a==1) c1++;
		if(a==2) c2++;
		if(a==3) c3++;
		if(a==4) c4++;
	}
	ll ret=INF;
	REP(i,min(c1,c3)+1) {
		int _c1=c1,_c2=c2,_c3=c3;
		ll buf=c4;
		buf+=i;
		_c1-=i;
		_c3-=i;
		if(_c1==0) buf+=(_c2+1)/2+_c3;
		else {
			buf+=_c3;
			buf+=_c1/4;
			_c1-=_c1/4*4;
			buf+=_c2/2;
			_c2-=_c2/2*2;
			if(_c2==0) {
				if(_c1!=0) buf++;
			}
			if(_c2==1) {
				if(_c1<=2) buf++;
				else buf+=2;
			}
		}
		ret=min(ret,buf);
	}
	cout<<ret<<endl;
}

Submission Info

Submission Time
Task C - スキーリフトの相乗り
User gazelle
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1251 Byte
Status AC
Exec Time 7 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 400 / 400
Status
AC × 49
Set Name Test Cases
All 00_sample00, 00_sample01, 100_corner0000, 100_corner0001, 100_corner0002, 100_corner0003, 10_small-0000, 10_small-0001, 10_small-0002, 10_small-0003, 10_small-0004, 10_small-0005, 10_small-0006, 10_small-0007, 10_small-0008, 10_small-0009, 20_special-0000, 20_special-0001, 20_special-0002, 20_special-0003, 20_special-0004, 20_special-0005, 20_special-0006, 20_special-0007, 20_special-0008, 20_special-0009, 20_special-0010, 20_special-0011, 20_special-0012, 20_special-0013, 20_special-0014, 30_large-0000, 30_large-0001, 30_large-0002, 30_large-0003, 30_large-0004, 30_large-0005, 30_large-0006, 30_large-0007, 30_large-0008, 30_large-0009, 80_combination-type00, 80_combination-type01, 80_combination-type02, 80_combination-type03, 80_combination-type04, 80_combination-type05, 80_combination-type06, 90_tayama-killer00
Case Name Status Exec Time Memory
00_sample00 AC 1 ms 256 KB
00_sample01 AC 1 ms 256 KB
100_corner0000 AC 1 ms 256 KB
100_corner0001 AC 1 ms 256 KB
100_corner0002 AC 1 ms 256 KB
100_corner0003 AC 1 ms 256 KB
10_small-0000 AC 1 ms 256 KB
10_small-0001 AC 1 ms 256 KB
10_small-0002 AC 1 ms 256 KB
10_small-0003 AC 1 ms 256 KB
10_small-0004 AC 1 ms 256 KB
10_small-0005 AC 1 ms 256 KB
10_small-0006 AC 1 ms 256 KB
10_small-0007 AC 1 ms 256 KB
10_small-0008 AC 1 ms 256 KB
10_small-0009 AC 1 ms 256 KB
20_special-0000 AC 1 ms 256 KB
20_special-0001 AC 1 ms 256 KB
20_special-0002 AC 1 ms 256 KB
20_special-0003 AC 1 ms 256 KB
20_special-0004 AC 1 ms 256 KB
20_special-0005 AC 1 ms 256 KB
20_special-0006 AC 1 ms 256 KB
20_special-0007 AC 1 ms 256 KB
20_special-0008 AC 1 ms 256 KB
20_special-0009 AC 1 ms 256 KB
20_special-0010 AC 1 ms 256 KB
20_special-0011 AC 1 ms 256 KB
20_special-0012 AC 1 ms 256 KB
20_special-0013 AC 1 ms 256 KB
20_special-0014 AC 1 ms 256 KB
30_large-0000 AC 7 ms 256 KB
30_large-0001 AC 7 ms 256 KB
30_large-0002 AC 7 ms 256 KB
30_large-0003 AC 7 ms 256 KB
30_large-0004 AC 7 ms 256 KB
30_large-0005 AC 7 ms 256 KB
30_large-0006 AC 7 ms 256 KB
30_large-0007 AC 7 ms 256 KB
30_large-0008 AC 7 ms 256 KB
30_large-0009 AC 7 ms 256 KB
80_combination-type00 AC 1 ms 256 KB
80_combination-type01 AC 1 ms 256 KB
80_combination-type02 AC 1 ms 256 KB
80_combination-type03 AC 1 ms 256 KB
80_combination-type04 AC 1 ms 256 KB
80_combination-type05 AC 1 ms 256 KB
80_combination-type06 AC 1 ms 256 KB
90_tayama-killer00 AC 1 ms 256 KB