akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush,heappop
n,m=map(int,input().split())
li=[[]for i in range(10**5+1)]
for i in range(n):
    a,b=map(int,input().split())
    li[a].append(b)

li2=[]
ans=0
for i in range(1,m+1):
    for x in li[i]:
        heappush(li2,-x)
    if li2:
        ans+=heappop(li2)
print(-ans)
        
    


Measured memory_bytes: 72224
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, x;
  cin >> n >> m >> x;
  vector<int> c(n);
  vector<vector<int>> A(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    for (auto &y : A[i])
      cin >> y;
  }
  int ans = 1 << 30;
  for (int mask = 0; mask < (1 << n); mask++) {
    int cost = 0;
    vector<int> skill(m, 0);
    for (int i = 0; i < n; i++) {
      if ((1 << i) & mask) {
        cost += c[i];
        for (int j = 0; j < m; j++) {
          skill[j] += A[i][j];
        }
      }
    }
    if (*min_element(skill.begin(), skill.end()) >= x)
      ans = min(ans, cost);
  }
  if (ans == (1 << 30))
    ans = -1;
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;

int main(){
	const int max = 20; 
	char str[max + 1];
	char c;
	int count = 0;
	while(cin.get(c)){
		str[count] = c;
		count++;
	}
	for(int i = 1; i <= count-1; i++)
		cout << str[count - i - 1];
	cout << endl;
	return 0;
}

Measured memory_bytes: 0
a,b,c,d=map(int,input().split())
def kosuu(a,b,c):
    if a%c==0:
        return (b-a)//c+1
    else:
        return(b-(a+(c-a%c)))//c+1

g=0
c1=c
d1=d
while c1!=0 and d1!=0:
    if c1<=d1:
        d1=d1%c1
    else:
        c1=c1%d1
if c1!=0:
    g=c1
else:
    g=d1

print(b-a+1-kosuu(a,b,c)-kosuu(a,b,d)+kosuu(a,b,c*d//g))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  string s,t;
  cin >> s >> t;
  int slen = sz(s);
  int tlen = sz(t);
  int ans = INF;
  rep(i,slen-tlen+1) {
    int cnt = 0;
    rep(j,tlen) {
      if(s[i+j]!=t[j]) {
        cnt++;
      }
    }
    chmin(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& input, vector<T>& v) { for (auto& elemnt : v)input >> elemnt; return input; }

int main() {
    init();

    int n;
    cin >> n;
    string s;
    cin >> s;

    VI a(4, 0);
    for (char c : s) {
        if (c < 'N')a[0]++;
        else if (c < 'a')a[1]++;
        else if (c < 'n')a[2]++;
        else a[3]++;
    }
    if (a[0] < a[1]) {
        a[1] -= a[0];
        a[0] = 0;
    }
    else {
        a[0] -= a[1];
        a[1] = 0;
    }
    if (a[2] < a[3]) {
        a[3] -= a[2];
        a[2] = 0;
    }
    else {
        a[2] -= a[3];
        a[3] = 0;
    }

    string d = "ANan";
    int sum = 0;
    FOR(i, 0, 4)sum += a[i];
    cout << sum << "\n";
    FOR(i, 0, 4)FOR(j, 0, a[i])cout << d[i];
    cout << "\n";
}



Measured memory_bytes: 3336
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int m1, d1, m2, d2;
    
    cin >> m1 >> d1;
    cin >> m2 >> d2;
    
    if(d2==1){
        
        cout << "1" << endl;
        
    } else {
        
        cout << "0" << endl;
        
    }

    return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

int main() {
    lint n;
    cin >> n;
    lint ans = 0;
    for (lint m = 1; m * m <= n; m++) {
        if (n / m == n % m) {
            ans += m;
        }
    }
    for (lint p = 1; p * p < n; p++) {
        if (n % p == lint(0)) {
            lint m = n / p - 1;
            if (lint(0) <= p and p < m) {
                ans += m;
            }
        }
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

#include <set>
#include <iterator>
using namespace std;
// using namespace __gnu_pbds;


#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define INF (ll)1e17
#define matrix vector<vector<ll> >

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )
#define maxbits 9
#define maxmask (1ll<<maxbits)
// typedef tree<pll, null_type, less<pll>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
const int  N=1e6 +10, M=(ll)1e9+1 ;
const int mod =(ll)1e9+7 ,sz=5, MAX=(ll)1e6+10;
string fir="Monocarp",sec="Bicarp";

void work(){
	ll n;
	cin >> n;
	ll a,c,b;
	a=n/3;
	b=n/5;
	c=n/15;
	n=(n*(n+1))/2;
	a=3*(a*(a+1))/2;
	b=5*(b*(b+1))/2;
	c=15*(c*(c+1))/2;
	cout << n-(a+b-c) ;

}

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);

	
	// precomp();
	ll t;
	// cin >> t;
	t=1;
	while(t--){
	        work();
	
	}

	return 0;
}
	

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
constexpr int MOD = 1000000007;

void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

int main ()
{
    int A,B,C;
    cin>>A>>B>>C;
    if( A< B and C<B and A<C){
        cout<<"Yes"<<endl;
        return 0;
    }
    if( B < A and B<C and C<A){
        cout<<"Yes"<<endl;
        return 0;
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

string s;

int n,t;

int main(){
    ios_base :: sync_with_stdio(0);
    cin >> s; n=s.length();
    for(int i=0;i<s.length();i++){
        if(s[i]=='S') t++;
        else if(t) n-=2,t--;
    }
    cout << n;
}


Measured memory_bytes: 720
#include <cstdio>
#include <vector>
using namespace std;

int main(){
	const int MAX_N = 1000;
	const int MAX_M = 1000;
	int N, M;
	int A[MAX_N], B[MAX_M], vote[MAX_N];
	int max_vote, out_num;
	
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++){
		scanf("%d", A + i);
	}
	for(int j = 0; j < M; j++){
		scanf("%d", B + j);
	}
	fill(vote, vote + N, 0);
	
	bool done;
	for(int j = 0; j < M; j++){
		done = false;
		for(int i = 0; i < N; i++){
			if(A[i] <= B[j] && !done){
				vote[i]++;
				done = true;
			}
		}
	}
	
	max_vote = 0;
	for(int i = 0; i < N; i++){
		if(max_vote < vote[i]){
			max_vote = vote[i];
			out_num = i + 1;
		}
	}
	
	printf("%d\n", out_num);
	
	return 0;
}

Measured memory_bytes: 1036
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
using namespace std;
typedef long long ll;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
//freopen("","r",stdin);
//freopen("","w",stdout);
int main(){
    int n;
    cin >> n;
    vector<ll> v(n);
    for(auto &i : v)cin >> i;
    int q;
    cin >> q;
    while(q--){
        ll t,x;
        cin >> t >> x;
        ll ans = 0;
        t--;
        ll aux = v[t];
        v[t] = x;
        fore(i,0,n){
            ans += v[i];
        }
        cout << ans << '\n';
        v[t] = aux;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



int main() {
	double T, X;
	cin >> T >> X;
	cout << T / X << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;

ll nCk[51][51];


int main(){
  nCk[0][0] = 1;
  for(int n = 0;n <= 49;n++){
    for(int k = 0;k <= n;k++){
      nCk[n+1][k] += nCk[n][k];
      nCk[n+1][k+1] += nCk[n][k];
    }
  }

  int N,P;
  cin >> N >> P;
  int cnt_even = 0;
  int cnt_odd = 0;
  for(int i = 0;i < N;i++){
    int A;
    cin >> A;
    if(A % 2)cnt_odd++;
    if(A % 2 == 0)cnt_even++;
  }

  if(P % 2){
    ll even_sum = 0;
    for(int i = 0;i <= cnt_even;i++)even_sum += nCk[cnt_even][i];

    ll odd_sum = 0;
    for(int i = 1;i <= cnt_odd;i+=2)odd_sum += nCk[cnt_odd][i];

    cout << even_sum * odd_sum << endl;
  }
  else{
    ll even_sum = 0;
    for(int i = 0;i <= cnt_even;i++)even_sum += nCk[cnt_even][i];

    ll odd_sum = 0;
    for(int i = 0;i <= cnt_odd;i+=2)odd_sum += nCk[cnt_odd][i];

    cout << even_sum * odd_sum << endl;
  }


}


Measured memory_bytes: 256
while True:
    n=input()
    if n==0:break
    R=[]
    for i in range(n):
        T=raw_input().split()
        L=T[0]
        P,A,B,C,D,E,F,S,M=map(int,T[1:])
        t=A+B+C+(D+E)*M
        m=F*S*M-P
        R.append((-m/float(t),L))
    for i in sorted(R):
        print i[1]
    print "#"

Measured memory_bytes: 4244
n = int(input())
a = list(map(int, input().split()))
ans1 = 0
s = 0
for i, v in enumerate(a):
    if i % 2 and s + v >= 0:
        ans1 += abs(-1 - s - v)
        s = -1
    elif i % 2 == 0 and s + v <= 0:
        ans1 += abs(1 - s - v)
        s = 1
    else:
        s += v

s = 0
ans2 = 0
for i, v in enumerate(a):
    if i % 2 and s + v <= 0:
        ans2 += abs(1 - s - v)
        s = 1
    elif i % 2 == 0 and s + v >= 0:
        ans2 += abs(-1 - s - v)
        s = -1
    else:
        s += v

print(min(ans1, ans2))

Measured memory_bytes: 14468
#include <iostream>
#include <cmath>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

void print_vector(vector<int> &num)
{
	for(int i = 0; i < num.size(); i++){
		if(i == 0){
			cout << num[i];
		}
		else{
			cout << " " << num[i];
		}
	}
	cout << endl;
}
int bubbleSort(vector<int> &A)
{	
	int count = 0;
	for(int i = 0; i <= A.size() - 1; i++){
		for(int j = A.size() - 1; j >= i + 1; j--){
			if(A[j] < A[j - 1]){
				count++;
				int a = A[j];
				A[j] = A[j - 1];
				A[j - 1] = a;
			}
		}
	}
	return count;
}


int main(void)
{
	int n;
	cin >> n;
	
	vector<int> A(n);
	
	for(int i = 0; i < n; i++){
		cin >> A[i];
	}
	
	int change = bubbleSort(A);

	print_vector(A);

	cout << change << endl;
	return 0;
}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    string n;
    cin >> n;
    bool ans = false;
    for(char &c : n)
    {
        if(c == '7') ans = true;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <algorithm>
#include<iostream>
#include<stdio.h>
#include <algorithm>
#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string>
#include<iomanip>
#include<queue>
#include<functional>
#include<cmath>
#define rep(i,n) for(int i=0; i<(int)n; i++)//n回繰り返す
using namespace std;
using ll = long long;
using P = pair<int, int>;
using graph = vector<vector<int>>;
int main() {
	int X,f,r,ans=0; cin >> X;
		f= X / 500;
		r = (X - 500 * f) / 5;
		ans = f * 1000 + 5 * r;
		cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(){

  int  arr[100], n,i,j,temp, mini, count=0;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    scanf("%d", &arr[i]);
  }
  for(i=0; i<n-1; i++){
    mini=i+1;
    for(j=i+1; j<n; j++){
      if(arr[j]<arr[mini]){
	mini=j;
      }
    }
    if(arr[mini]<arr[i]){
      temp=arr[i];
      arr[i]=arr[mini];
      arr[mini]=temp;
      count++;
    }
  }
  for(i=0;i<n;i++){
    printf("%d",arr[i]);
    if(i<n-1){
      printf(" ");
    }
  }
  printf("\n");
  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 604
#include <iostream>
using namespace std;
int main()
{
    // 整数の入力
    int a[5], b[5];
    int total_time;
    int amari;

    amari = 10;
    for(int i; i < 5; i++){
        cin >> a[i];
        if(a[i] % 10 == 0){
            total_time = a[i] + total_time;
        }else{
            total_time = (a[i] / 10) * 10 + 10 + total_time;
            if(a[i] % 10 < amari){
                amari = a[i] % 10;
            }
        }
    }


    cout << (total_time + amari -10) << endl ;
 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)) //整数型のまま切り上げ演算する
#define PI 3.14159265359
typedef long long LL;
template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> inline T gcd(T x, T y) { if (y == 0) { return x; } else if (x == 0) { return y; }return gcd(y, x % y); }
template<class T> inline T lcm(T x, T y) { return (x * y) / gcd(x, y); }
template<class T> inline vector<T> convert_to_binary_number(T x) { vector<T> binary_num; while (x != 1) { binary_num.push_back(x % 2); x /= 2; } binary_num.push_back(1); return binary_num; }
template<class T> inline void print_vector(vector<T> vec) { for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl;}
const LL MOD = 1e9 + 7;
const LL INF = 1LL << 60;

enum { t, u, r, l, d, b };

int main(void){
    string S;
    cin >> S;
    
    for(int i = 0; i < S.size(); i++) {
        if(i%2 == 0){
            if(S[i] != 'R' and S[i] != 'U' and S[i] != 'D'){
                cout << "No" << endl;
                return 0;
            }
        }else{
            if(S[i] != 'L' and S[i] != 'U' and S[i] != 'D'){
                cout << "No" << endl;
                return 0;
            }
        }
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
n,a=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(n*50+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(j*50+1):
            if k<x[i-1]:
                dp[i][j][k]=dp[i-1][j][k]
            else:
                dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
ans=0
for i in range(1,n+1):
    ans+=dp[-1][i][i*a]
print(ans)

Measured memory_bytes: 62960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,c[51],d[51][21][2],v[51][21][2],a=1e18;
string s[51];

ll fnc(ll b,ll p,ll g) {
   if(p == s[b].size()) return 0;
   ll &e = v[b][p][g];
   ll &m = d[b][p][g];
   if(e) return m;
   e = 1, m = 1e18;

   ll l = 1;
   if(!g) {
      for(int j=p, k=s[b].size()-1; j<k; j++, k--) {
         if(s[b][j] != s[b][k]) l = 0;
      }
   }
   else {
      for(int j=0, k=p; j<k; j++, k--) {
         if(s[b][j] != s[b][k]) l = 0;
      }
   }
   if(l) return m = 0;

   for(int i=0; i<n; i++) {
      ll y = 1;
      int j, k;
      if(!g) {
         for(j=p, k=s[i].size()-1; j<s[b].size() && k>=0 && y; j++, k--) {
            if(s[b][j] != s[i][k]) y = 0;
         }
         if(y) {
            if(k < 0) m = min(m, c[i] + fnc(b, j, 0));
            else m = min(m, c[i] + fnc(i, k, 1));
         }
      }
      else {
         for(j=p, k=0; k<s[i].size() && j>=0 && y; j--, k++) {
            if(s[b][j] != s[i][k]) y = 0;
         }
         if(y) {
            if(j < 0) m = min(m, c[i] + fnc(i, k, 0));
            else m = min(m, c[i] + fnc(b, j, 1));
         }
      }
   }
   return m;
}

int main() {
   cin >> n;
   for(int i=0; i<n; i++) cin >> s[i] >> c[i];
   for(int i=0; i<n; i++) a = min(a, c[i] + fnc(i, 0, 0));
   cout<<(a==1e18 ? -1 : a)<<endl;
}


Measured memory_bytes: 3652
class Graph
  def initialize(id, next_id)
    @id = id
    @next_id = next_id
    @d = -1
  end

  attr_accessor :id, :next_id, :d
end


def breadth_first_search(first)
  first.d = 0
  queue = [first]

  until queue.empty? do
    now = queue.shift
    now.next_id.each do |x|
      if @array[x].d == -1
        @array[x].d = now.d+1
        queue << @array[x]
      end
    end
  end
end


@array = [nil]

n = gets.to_i.times do
  input = gets.split(" ").map{|x| x.to_i}
  u = input.shift
  k = input.shift
  @array << Graph.new(u, input)
end

breadth_first_search(@array[1])

1.upto n do |x|
  printf "%d %d\n" ,@array[x].id ,@array[x].d
end



Measured memory_bytes: 6904
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

int main() {
    int K, Q; scanf("%d%d", &K, &Q);
    vector<ll> D(K);
    for(int i=0; i<K; i++) scanf("%lld", &D[i]);

    while(Q--) {
        ll N, X, M; scanf("%lld%lld%lld", &N, &X, &M);
        vector<ll> E = D;
        for(auto &e : E) e %= M;
        ll ans = N - 1, mod = (N - 1) % K, div = (N - 1) / K;

        // equal
        for(int i=0; i<K; i++) {
            if(E[i] == 0) ans -= div + (i < mod);
        }

        // less
        ll sum = 0;
        for(int i=0; i<K; i++) sum += E[i];

        ll a = X + sum * div, b = X;
        for(int i=0; i<mod; i++) a += E[i];
        ans -= a / M - b / M;

        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int main(int argc, char *argv[]){

  int A , B;
  cin >> A >> B;

  if((A+B)%3 == 0 || A%3 == 0 || B%3 == 0)
    printf("Possible\n");
  else
    printf("Impossible\n");

  return 0;
}


Measured memory_bytes: 256
//////////////////////////////
// Author: whatisit
// Date: 2020-05-14 01:24 
//////////////////////////////
#include <bits/stdc++.h>
using namespace std;

long long n, k;
void solve() {
	cin >> n >> k;
	n %= k;
	if (n > (k/2)) cout << k-n;
	else cout << n;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

Measured memory_bytes: 3624
from math import sqrt
def f(x):
    res = True if x>1 else False
    for i in range(2,int(sqrt(x))+1):
        if x%i==0:
            res = False
            break
    return res
ans = []
while True:
    a,d,n = map(int,input().split())
    if a+d+n==0:
        break
    k = 1 if f(a) else 0
    while True:
        if k==n:
            ans.append(a)
            break
        a += d
        if f(a):
            k+=1
for i in ans:
    print(i)


Measured memory_bytes: 5692
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define SZ(i) int(i.size())
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#endif

const int MAXN = 1000006;
const ll MOD = 1000000007;

int n;
string str1, str2;
vector<bool> dom;
/*********************GoodLuck***********************/
int main () {
    IOS();
    cin >> n >> str1 >> str2;
    REP (i, n) {
        if (str1[i] == str2[i]) {
            dom.emplace_back(1);
        } else {
            dom.emplace_back(0);
            i++;
        }
    }

    ll cur = dom[0] ? 3 : 6;
    for (int i=1; i<SZ(dom); i++) {
        if (dom[i]) {
            if (dom[i-1]) {
                cur = cur * 2 % MOD;
            }
        } else {
            if (!dom[i-1]) {
                cur = cur * 3 % MOD;
            } else {
                cur = cur * 2 % MOD;
            }
        }
    }

    cout << cur << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>> d(n+1,vector<int>(m,0));
    for(int i = 0;i < n;++i) {
        int t;
        cin>>t;
        --t;
        ++d[i+1][t];
    }
    for(int i = 0;i < m;++i) {
        for(int j = 0;j < n;++j) {
            d[j+1][i]+=d[j][i];
        }
    }

    vector<int> mae(1<<m,0);
    for(int bit = 0;bit < 1<<m;++bit) {
        for(int j = 0;j < m;++j) {
            if((bit & (1<<j))==0)continue;
            mae[bit]+=d[n][j];
        }
    }

    vector<int> dp(1<<m,n+1);
    dp[0]=0;
    for(int bit = 1;bit < 1<<m;++bit) {
        for(int j = 0;j < m;++j) {
            if((bit & (1<<j))==0)continue;
            int nv=dp[bit-(1<<j)];
            nv+=mae[bit]-mae[bit-(1<<j)]-(d[mae[bit]][j]-d[mae[bit-(1<<j)]][j]);
            dp[bit]=min(dp[bit],nv);
        }
    }
    cout<<dp.back()<<endl;
    return 0;
}



Measured memory_bytes: 22612
using System;

class Program
{
    static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');

        int a = int.Parse(str[0]);
        int b = int.Parse(str[1]);

        int d = a / b;
        int r = a % b;
        double a2 = a;
        double b2 = b;
        double f = a2 / b2;

        Console.WriteLine("{0} {1} {2:f5}", d,r,f);
    }
}

Measured memory_bytes: 9128
import sys
import numpy as np
input = sys.stdin.readline


def log(*args):
    print(*args, file=sys.stderr)


def main():
    np.set_printoptions(threshold=20)
    n, k = map(int, input().rstrip().split())
    ds = set(map(int, input().rstrip().split()))
    for i in range(n, 1000000):
        continue_flag = False
        for c in str(i):
            if int(c) in ds:
                continue_flag = True
        if continue_flag:
            continue
        else:
            print(i)
            return


if __name__ == '__main__':
    main()


Measured memory_bytes: 27096
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    string S[s.size()];
    bool flag = true;

    for(int i=0; i<s.size(); i+=2){
        if(s[i] != 'h' || s[i+1] != 'i') flag=false;
    }
    
    if(flag == true){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <iostream>
#include <locale>
#include <numeric>
#include <string>
#include <vector>
 
using namespace std;

int main(int argc, char const *argv[]) {
    cin.tie(0);

    int r;cin>>r;
    int g;cin>>g;
    int b;cin>>b;
    int n;cin>>n;
    int ans=0;

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if((n-r*i-g*j)%b==0 && (n-r*i-g*j)/b>=0 && (n-r*i-g*j)/b <= 3000)ans++;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
a[22],n,j,i;f(i,s){return s>0&&i-n?f(i+1,s-a[i])+f(i+1,s):!s;}main(m){for(scanf("%d",&n);j<n;j++)scanf("%d",a+j);for(scanf("%d",&m);i++<m;)scanf("%d",&j),puts(f(0,j)?"yes":"no");return 0;}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define prique priority_queue
#define inf 1145141919364364
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
typedef pair<ll, ll>P;
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
ll n,k;
string s;
signed main(){
	ll memo=0;
	cin>>n>>k>>s;
	rep(i,n-1){
		if(s[i]!=s[i+1])memo++;
	}
	cout<<n-1-max((ll)0,(memo-2*k))<<endl;
}



Measured memory_bytes: 512
#include <stdio.h>

int partition(int *A, int p, int r){
  int x,i,j,k;
  
  x=A[r];
  i=p-1;
  for(j=p; j<r; j++)
    if(A[j]<=x){
      i=i+1;
      k=A[i];
      A[i]=A[j];
      A[j]=k;
    }
  
  k=A[i+1];
  A[i+1]=A[r];
  A[r]=k;

  return i+1;
}

int main(){
  int i,A[100000],n,p;

  scanf("%d",&n);
  for(i=0; i<n; i++)
    scanf("%d",&A[i]);

  p=partition(A,0,n-1);

  for(i=0; i<p; i++)
    printf("%d ",A[i]);
  printf("[%d] ",A[i]);
  for(i=p+1; i<n-1; i++)
    printf("%d ",A[i]);
  printf("%d\n",A[i]);
  

  return 0;
}
      
      
  



Measured memory_bytes: 2116
#include<sstream>
#include<fstream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
#include<ctime>
#include<locale>
using namespace std;
char c[101][101];
int main()
{
    long a,b;
    scanf("%d%d",&a,&b);getchar();
    for(long i=0;i<a;i++)
    {
        for(long j=0;j<b;j++)scanf("%c",&c[i][j]);
        getchar();
    }
    for(long i=0;i<b+2;i++)printf("#");printf("\n");
    for(long i=0;i<a;i++)
    {
        printf("#");
        for(long j=0;j<b;j++)
            printf("%c",c[i][j]);
        printf("#");
        printf("\n");
    }
    for(long i=0;i<b+2;i++)printf("#");
	return 0;
}


Measured memory_bytes: 128
class Dice
  def initialize(n)
    @n = n
  end
  #     ^N
  #    n[0]:top
  # [3] [1] [2] [4]
  #     [5]:bottom
  #     vS
  attr_reader :n

  def rotate(d)
    case d
    when "N"
      @n = [@n[1], @n[5], @n[2], @n[3], @n[0], @n[4]]
    when "S"
      @n = [@n[4], @n[0], @n[2], @n[3], @n[5], @n[1]]
    when "E"
      @n = [@n[3], @n[1], @n[0], @n[5], @n[4], @n[2]]
    when "W"
      @n = [@n[2], @n[1], @n[5], @n[0], @n[4], @n[3]]
    else
      raise
    end
  end
end

d=Dice.new(gets.split.map(&:to_i))
gets.chomp.chars{|c|d.rotate(c)}
p d.n[0]




Measured memory_bytes: 6872
import numpy


l, r = map(int, input().rstrip().split())

# let p, q, s, t >= 0
# l = 2019 * s + p
# r = 2019 * t + q

s = l // 2019
p = l % 2019

t = r // 2019
q = r % 2019

if s == t:
  # i = 2019 * s + x
  # j = 2019 * s + y
  x = numpy.arange(p, q + 1, 1)
  rem = numpy.dot(x.reshape(-1, 1), x.reshape(1, -1))
  rem %= 2019
  row, col = rem.shape
  rem += numpy.identity(row, dtype=int) * 2019
  min_rem = numpy.amin(rem)
  
  print(min_rem)

else:
  print(0)



Measured memory_bytes: 105560
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

typedef pair<int, int> PII;

int main() {
	int n, a;

	cin >> n;
	vector<PII> pairs(n);
	for (int i = 0; i < n; i++) {
		cin >> a;
		pairs[i] = make_pair(a, i);
	}

	sort(pairs.begin(), pairs.end());

	vector<int> types(2, 0);
	int shift = 2e9;
	for (int i = 0; i < n; i++) {
		// printf("%d %d\n", pairs[i].first, pairs[i].second);
		int type = (i - pairs[i].second + shift) % 2;
		types[type]++;
	}

	int ans = types[1] / 2;

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n,d,i;
  cin>>n;
  vector<int> a(n);
  for (i=0;i<n;i++) cin>>a.at(i);
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  d=0;
  for (i=0;i<n;i++) {
    if (i%2==0) d+=a.at(i);
    else d-=a.at(i);
  }
  cout<<d<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define mk make_pair
#define pb push_back
ll modexp(ll x,ll y){
    if(y==0)return 1;
    ll ans=modexp(x,y/2);
    ans=ans*ans;
    if(y&1)ans*=x;
    return ans;
}
int main(){
   ll a;cin>>a;
   ll ans=modexp(a,1)+modexp(a,2)+modexp(a,3);
   cout<<ans<<endl;
    return 0;
}

/*int main(){
    ll n,m,k;
    cin>>n>>m>>k;
     vector<ll> a;
     vector<ll> b;
     for(int i=0;i<n;i++){int x;cin>>x;a.pb(x);}
    for(int i=0;i<m;i++){int x;cin>>x;b.pb(x);}
    for(int i=1;i<n;i++)a[i]+=a[i-1];
    for(int i=1;i<m;i++)b[i]+=b[i-1];
    ll ans=-1;
    for(int i=0;i<m;i++){
     if(k>b[i]){
         ll val=0;
        if(upper_bound(a.begin(),a.end(),k-b[i])!=a.end())val= upper_bound(a.begin(),a.end(),k-b[i])-a.begin();
        else val=a.size();
        val+=(i+1);
        ans=max(val,ans);
     }   
    }
    cout<<ans<<endl;
    return 0;
}*/

Measured memory_bytes: 3640
// Area of Polygon
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079
// 
// 

#include <iostream>
#include <complex>
#include <cmath>
#include <cstdio>

using namespace std;

typedef std::complex<double> xy_t;
xy_t P[110];

double dot_product(xy_t a, xy_t b) { return (conj(a)*b).real(); }
double cross_product(xy_t a, xy_t b) { return (conj(a)*b).imag(); }

xy_t projection(xy_t p, xy_t b) { return b*dot_product(p,b)/norm(b); }

double calc_area(xy_t A, xy_t B, xy_t C){ //面積を計算
    xy_t a = B - A, b = C - A; //ベクトルの始点を原点に移動
    double area = abs(cross_product(a, b)/2.0);
    return area;
}

int main(){
    int N = 0;
    double x, y;
    while(~scanf("%lf,%lf", &x, &y)){
        P[N++] = xy_t(x, y);
    }  

    double sum = 0.00000;
    
    xy_t A = P[0];
    
    for(int i = 0; i < (N-2); ++i){
        xy_t B = P[i+1], C = P[i+2];
        sum += calc_area(A, B, C);
    }

    printf("%.6f\n", sum);
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define dbg(var) {std::cout << #var << "  = " << var << nl;}
#define vi vector<int>
typedef long long ll;

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 
	
	int r , d , x;
	cin >> r >> d >> x;
	
	rep(i , 10)
	{
		x = r * x - d;
		die(x);
	}
	
	return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
s = []
t = []
n.times do
  s.push gets.chomp
end
m = gets.chomp.to_i
m.times do
  t.push gets.chomp
end
max = 0
s.uniq.each do |e|
  diff = s.count(e) - t.count(e)
  max = diff if max < diff
end
puts max


Measured memory_bytes: 1788
from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]

y_start, x_start = 0, 0
y_goal, x_goal = Height-1, Width-1

min_step_map = [[-1]*Width for _ in range(Height)]
min_step_map[y_start][x_start] = 0
reserch_point = deque()
reserch_point.append([y_start, x_start])
while len(reserch_point) > 0:
    y_now, x_now = reserch_point.popleft()

    for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
        y_next, x_next = y_now+dy, x_now+dx
        if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
            continue

        if y_next == y_goal and x_next == x_goal:
            min_step_map[y_goal][x_goal] = min_step_map[y_now][x_now] + 1
            break

        if Map[y_next][x_next] == '.' and min_step_map[y_next][x_next] == -1:
            min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
            reserch_point.append([y_next, x_next])
        
    else:
        continue
    break

else:
    print(-1)
    exit()

min_step = min_step_map[y_goal][x_goal]
count_black = 0
for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            count_black += 1

# Since the starting point is not included in 'min_step',
# it is excluded from the total number of maps.
total_point = Height * Width - 1

score = total_point - count_black - min_step
print(score)

Measured memory_bytes: 40688
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define endl "\n"
#define sz(x) ((ll)(x).size())
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define prt(x) cout << (x)
#define prtl(x) cout << (x) << endl
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define rrep(i,a,b) for(ll i=a; i>b; i--)
#define mp(a, b) make_pair(a, b)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define debug(v) cout << #v<< ": " << v <<endl;
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using vvc = vector<vector<char>>;
using ll = long long int;
using P = pair<long long int, long long int>;
using Map = map<long long int, long long int>;
ll INF = 1LL<<60;
ll M = 1000000007;

int main(){
    ll N, T; cin >> N >> T;
    vll A(N+1), B(N+1);
    rep(i, 1, N+1){
        cin >> A[i] >> B[i];
    }
    vvll dp(N+1, vll(T+1));
    rep(i, 0, T+1){
        dp[0][i] = 0;
    }
    rep(i, 1, N+1){
        rep(j, 0, T){
            if(j < A[i]){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]]+B[i]);
            }
        }
    }
    vvll dpp(N+1, vll(T+1));
    rep(i, 0, T){
        dpp[0][i] = 0;
    }
    reverse(all(A)); reverse(all(B));
    rep(i, 1, N+1){
        //prt(A[i-1]); prt(" ");
        rep(j, 0, T){
            if(j < A[i-1]){
                dpp[i][j] = dpp[i-1][j];
            }else{
                dpp[i][j] = max(dpp[i-1][j], dpp[i-1][j-A[i-1]]+B[i-1]);
            }
        }
    }
    //prt(endl);
    reverse(all(A)); reverse(all(B));
    ll x = 0;
    rep(i, 1, N+1){
        ll mx = 0;
        rep(j, 0, T){
            ll a = dp[i-1][j];
            ll b = dpp[N-i][T-1-j];
            chmax(mx, a+b);
        }
        chmax(x, mx+B[i]);
    }
    prtl(x);
    return 0;
}



Measured memory_bytes: 144224
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

fn main() {
    input! {x:usize};
    let mut p = 0;
    let mut ans = 0;
    loop {
        p += x;
        ans += 1;
        if p % 360 == 0 {
            break;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2192
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

#ifdef _DEBUG
#include "../../library/library/debug_template.cpp"
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

template<class T>
inline bool chmin(T& a, const T b) { return a > b && (a = b, true); }

int main() {

	int N;
	cin >> N;

	vector<lint> A(N + 1);
	for (int i = 0; i <= N; i++) cin >> A[i];

	// if N not 0 B_0 = 1
	// B_(i-1) <= A_i + B_i <= 2*B_(i-1)
	// B_N=0
	vector<lint> B(N + 1);
	B[0] = 1;
	for (int i = 1; i <= N; i++) {
		if (B[i - 1] > LINF) {
			B[i] = LINF - A[i];
		}
		else {
			B[i] = 2 * B[i - 1] - A[i];
		}
	}
	DMP(B);
	DMP(accumulate(B.begin(), B.end(), 0LL));

	// A_i + B_i <= 2**i
	for (int i = 0; i <= N; i++) {
		if (i >= 50) {
			chmin(B[i], LINF - A[i]);
		}
		else {
			chmin(B[i], (1LL << i) - A[i]);
		}
	}
	DMP(B);
	DMP(accumulate(B.begin(), B.end(), 0LL));

	lint sum = 0;
	for (int i = N; i >= 0; i--) {
		chmin(B[i], sum);
		sum += A[i];
	}
	DMP(B);
	DMP(accumulate(B.begin(), B.end(), 0LL));

	lint ans = 0;
	if (any_of(B.begin(), B.end(), [](auto b) { return b < 0; }) || A[0] != 0 && N != 0 || A[0] != 1 && N == 0) {
		ans = -1;
	}
	else {
		ans = accumulate(A.begin(), A.end(), 0LL) + accumulate(B.begin(), B.end(), 0LL);
	}

	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 4784
#import<cstdio>
int main(){int K,n,i=-1,j,k;scanf("%d",&K);printf("%d",n=(K+3)/4*2);while(++i<n){puts("");j=-1;while(++j<n)printf("%d ",((k=i%2*n+(i+j)%n)>=K?k-n:k)%K+1);}}

Measured memory_bytes: 1152
import java. util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);

		int k = scan.nextInt();
		String s = scan.next();

		char[] c = s.toCharArray();

		if(c.length<=k) {
			System.out.println(s);
		}else {
			for(int i=0;i<k;i++) {
				System.out.print(c[i]);
			}
			System.out.println("...");
		}



	}

}


Measured memory_bytes: 35820
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N) cin >> a[i];
    sort(all(a));
    cout << a[N-1] - a[0] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, M;
  cin >> N >> M;
  vector<long long> dp(N+1, 0);
  vector<bool> broken(N+1, false);
  for (int i = 0; i < M; i++) {
    int n;
    cin >> n;
    broken[n] = true;
  }
  dp[0] = 1;
  dp[1] = 1;
  int mod = 1000000007;
  for (int i = 2; i <= N; i++) {
    if (!broken[i]) {
      if (!broken[i-1]) dp[i] += dp[i-1];
      if (!broken[i-2]) dp[i] += dp[i-2];
    }
    dp[i] %= mod;
  }
  cout << dp[N]%mod << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 1 << 25;
int cost[11][11][11][11][55];// depth, pos, l, r, oxy


struct S {
	int depth, pos, l, r, oxy, sum;
	bool operator <(const S& x) const {
		return sum > x.sum;
	}
};
void save(S s, int c) {
	cost[s.depth][s.pos][s.l][s.r][s.oxy] = c;
}
int ret(S s) {
	return cost[s.depth][s.pos][s.l][s.r][s.oxy];
}

int c[10][10];

int main() {
	int W, H, f, M, O;
	while(cin >> W >> H, W + H) {
		cin >> f >> M >> O;
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				cin >> c[i][j];
			}
		}

		if(O <= 1) {
			cout << "NA" << endl;
			continue;
		}

		priority_queue<S> q;
		fill((int*)begin(cost), (int*)end(cost), INF);
		for(int j = 0; j < W; j++) {
			S ns = { 0, j, j, j, O - 1, 0 };
			if(c[0][j] < 0) ns.sum = -c[0][j];
			else ns.oxy = min(ns.oxy + c[0][j], M);
			save(ns, ns.sum);
			q.push(ns);
		}

		int ans = INF;
		while(q.size()) {
			S s = q.top();
			q.pop();
			if(s.depth == H - 1) {
				ans = min(ans, s.sum);
				break;
			}
			if(ret(s) < s.sum || s.oxy <= 1) continue;

			for(int i = 0; i < 3; i++) {
				S ns = { s.depth, s.pos, s.pos, s.pos, s.oxy - 1, s.sum };

				if(i == 0) {
					ns.depth++;
					ns.l = ns.r = ns.pos;
				}
				if(i == 1 && s.pos != 0) {
					ns.pos--;
					if(s.pos == s.l) ns.l--;
				}
				if(i == 2 && s.pos != W - 1) {
					ns.pos++;
					if(s.pos == s.r) ns.r++;
				}

				int x = c[ns.depth][ns.pos];
				if(x < 0) ns.sum -= x;
				else ns.oxy = min(ns.oxy + x, M);

				if(ret(ns) > ns.sum) {
					save(ns, ns.sum);
					q.push(ns);
				}
			}
		}

		if(ans > f) {
			cout << "NA" << endl;
		}
		else {
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 6308
n = int(input())
H = list(map(int, input().split()))
min_H = min(H)

if min_H == 0:
    ans = 0
else:
    ans = min_H
    H = list(map(lambda  x: x -min_H, H))
#print(H, ans)


#for i in range(1,max(H)+1):

for j in range(n):
    #print(H, ans)
    while 0 < H[j]:
        '''H[j] -= 1
        ans += 1'''
        c = j
        end = j
        while end < n:
            #print('---', H)
            if H[end] > 0:
                end += 1
            else:
                break
        if H[j:end]:
            #print(H[j:end])
            min_H = min(H[c:end])
            ans += min_H
            for k in range(c,end):
                H[k] -= min_H
        

            '''print('---', H)
            if H[c+1] > 0:
                H[c+1] -= 1
                c += 1
            else:
                H[j] -= 1
                break'''
print(ans)
#print(H)




Measured memory_bytes: 3064
def input_nums():
    return [ int(i) for i in input().split(" ") ]
nums = input_nums()
A = nums[0]
B = nums[1]
T = nums[2]

biscut = 0
cnt = 1
for t in range(T):
	if (cnt==A):
		biscut += B
		cnt=1
	else:
		cnt+=1
print(biscut)

Measured memory_bytes: 3064
using CompLib.Util;
using System;

public class Program
{

    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        int z = sc.NextInt();
        int w = sc.NextInt();
        int[] a = sc.IntArray();

        // 全部Xが取る
        var s = Math.Abs(a[n - 1] - w);
        // xが一枚残して取る
        var t = n >= 2 ? Math.Abs(a[n - 2] - a[n - 1]) : int.MinValue;

        Console.WriteLine(Math.Max(s, t));
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;
    class Scanner
    {
        private int _index;
        private string[] _line;
        const char separator = ' ';

        public Scanner()
        {
            _index = 0;
            _line = new string[0];
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(separator);
                _index = 0;
            }
            return _line[_index++];
        }
        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(separator);
            _index = _line.Length;
            return _line;
        }
        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
    }
}

Measured memory_bytes: 11348
// Exhaustive Search
#include <stdio.h>
#define MAX 500000
#define INFTY 1000000000

void merge(int*, int, int, int);
void mergeSort(int*, int, int);

int count=0;

int main(){
  int i, n, A[MAX];

  scanf("%d", &n);
  for(i=0; i < n; i++){
    scanf("%d", &A[i]);
  }
  
  mergeSort(A, 0, n); // マージソートを実行

  for(i=0; i < n; i++){
    if(i != 0)printf(" ");
    printf("%d", A[i]);
  }
  printf("\n%d\n", count);
    
  return 0;
}

void merge(int *A, int left, int mid, int right){
  int i, j, k, n1, n2, L[MAX], R[MAX];
  n1 = mid - left;
  n2 = right - mid;
  for(i=0; i < n1; i++){
    L[i] = A[left + i];
  }
  for(i=0; i < n2; i++){
    R[i] = A[mid + i];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j = 0;
  for(k=left; k < right; k++){
    if(L[i] <= R[j]){
      A[k] = L[i];
      i++;
      count++;
    }
    else{
      A[k] = R[j];
      j++;
      count++;
    }
  }
}

void mergeSort(int *A, int left, int right){
  int mid;
  if(left + 1 < right){
    mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}



Measured memory_bytes: 5716
<?php
$mark = array('S'=>0,'H'=>1,'C'=>2,'D'=>3);
$cards = array_fill(1, 52, false);
$n = (int)fgets(STDIN);
$res = '';
while (--$n >= 0) {
  $set = explode(' ', trim(fgets(STDIN)));
  $cards[$mark[$set[0]]*13+(int)$set[1]] = true;
}
foreach($mark as $key => $val) {
  for ($i = 1; $i <= 13; $i++) {
    if (!$cards[$mark[$key]*13+$i]) $res = $res."$key $i".PHP_EOL;
  }
}
echo $res;

Measured memory_bytes: 15332