akhauriyash/Code-Regression huggingface dataset:
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    solve();
}

#ifndef TEMPLATE_USED
#include "../template/template.hpp"
#endif

template<int m>
struct MInt{
    //static int m;

    ll x;
    MInt(ll x=0):x((x%m+m)%m){}

    MInt operator-()const{return MInt(-x);}
    MInt operator+(const MInt &p)const{return MInt(*this)+=p;}
    MInt operator-(const MInt &p)const{return MInt(*this)-=p;}
    MInt operator*(const MInt &p)const{return MInt(*this)*=p;}
    MInt operator/(const MInt &p)const{return MInt(*this)/=p;}

    MInt &operator+=(const MInt &p){
        if((x+=p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator-=(const MInt &p){
        if((x+=m-p.x)>=m)x-=m;
        return *this;
    }
    MInt &operator*=(const MInt &p){
        (x*=p.x)%=m;
        return *this;
    }
    MInt &operator/=(const MInt &p){
        return *this*=p.inv();
    }

    MInt pow(ll n)const{
        MInt ret(1),mul(x);
        while(n){
            if(n&1)ret*=mul;
            mul*=mul;
            n>>=1;
        }
        return ret;
    }
    MInt inv()const{
        //return pow(m-2);
        int a=x,b=m,u=1,v=0,t;
        while(b){
            t=a/b;
            swap(a-=t*b,b);
            swap(u-=t*v,v);
        }
        return MInt(u);
    }

    friend ostream& operator<<(ostream& os,const MInt& a) {return os<<a.x;}
};
//int MInt::m=0;
using mint=MInt<(int)1e9+7>;

mint dp[2][100005];

void solve(){
    /* (´~`) */
    string s;cin>>s;
    ll n=s.size();
    dp[0][0]=1;
    rep(i,s.size()){
        if(s[i]=='0'){
            dp[0][i+1]=dp[0][i];
            dp[1][i+1]=dp[1][i]*3;
        }else{
            dp[0][i+1]=dp[0][i]*2;
            dp[1][i+1]=dp[0][i]+dp[1][i]*3;
        }
    }
    mint ans=dp[0][n]+dp[1][n];
    cout<<ans<<endl;
}

Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int Mod = 1000000007;
class mll {
public:
	long long x;
	mll(long long x = 0) : x((x% Mod + Mod) % Mod) {};
	void operator += (const mll& a) {
		if ((x += a.x) >= Mod) x -= Mod;
	}
};
//see answer
int main() {
	int N;
	cin >> N;
	vector<int> C(N + 1);
	for (int i = 1; i <= N; i++) cin >> C[i];
	vector<mll> DP(N + 1);
	map<int, mll> Memo;
	for (int i = 0; i <= N; i++) {
		if (i <= 1) DP[i] = 1;
		else DP[i] = Memo[C[i]];
		if (i == 0) Memo[C[1]] = DP[0];
		else if (i < N && C[i] != C[i + 1]) Memo[C[i + 1]] += DP[i];
	}
	cout << DP[N].x << endl;
}

Measured memory_bytes: 15104
N = int(input())
A = list(map(int,input().split()))

L = set()
cnt = 0
for a in A:
    c = a//400
    if c >= 8:
        cnt += 1
    else:
        L.add(a//400)
if len(L) == 0:
    print(1,cnt)
else:
    print(len(L),len(L)+cnt)


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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vst = vector<st>;
using vchar = vector<char>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
ll mod = 1000000007;

int main(){
  ll n, k;
  cin >> n >> k;
  if(k % 2 == 0){
    ll ans = k / 2 - abs(k / 2 - n % k);
    cout << ans << endl;
  }
  else{
    if(n % k <= k / 2) cout << n % k << endl;
    else cout << k - n % k << endl;
  }
}

Measured memory_bytes: 256
s=input()
ans=1000
for i in range(26):
  if chr(97+i) not in s:continue
  S=s
  cnt=0
  while(len(set(S)))!=1:
    cnt+=1
    t=""
    for j in range(len(S)-1):
      if S[j] == chr(97+i) or S[j+1] == chr(97+i):
        t+=chr(97+i)
      else:
        t+=S[j]
    S=t
  ans=min(cnt,ans)
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <stdio.h>
#include <cctype>
#include <cmath>
#include <math.h>
using namespace std;

int isprime(int x){
  if (x<2) return 0;
  if (x==2) return 1;
  if (x%2==0) return 0;
  for (int i=3;i<=sqrt(x);i+=2){
    if (x%i==0) return 0;
  }
  return 1;
}

int main(){
  int n,cnt=0;
  int a[10000];
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if (isprime(a[i])) cnt++;
  }
  cout << cnt <<endl;
}



Measured memory_bytes: 3112
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	int a,b,c,d,sum=0;
	char s,t;

    cin>>s>>t;
    if(s<t)cout<<"<";
    if(s>t)cout<<">";
    if(s==t)cout<<"=";
	
	return 0;
}
	

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector>
using namespace std;

long long int N, M;
string S;

int main(){
	int S, W;

    cin >> S >> W;

    if(S <= W){
        cout << "unsafe";
    } else {
        cout << "safe";
    }
}   

Measured memory_bytes: 3592
#include <bits/stdc++.h>
// #include "/usr/local/include/cxx_pretty_print/cxx_pretty_print.hpp"

using namespace std;
/* type aliases */
using i32 = int32_t; using ui32 = uint32_t; using i64 = int64_t; using ui64 = uint64_t; using i128 = __int128;
using f32 = float;   using f64  = double;   using f80 = long double;
using PII = pair<i32, i32>; using PLL = pair<i64, i64>; using PFF = pair<f32, f32>; using PDD = pair<f64, f64>;
using VB  = vector<bool>;   using VS  = vector<string>;
using VI  = vector<i32>;    using VL  = vector<i64>;    using VF  = vector<f32>;    using VD  = vector<f64>;
using VVI = vector<VI>;     using VVL = vector<VL>;     using VVF = vector<VF>;     using VVD = vector<VD>;
using VPI = vector<PII>;    using VPL = vector<PLL>;    using VPF = vector<PFF>;    using VPD = vector<PDD>;
/* constants */
constexpr i64 mod = 1000000007;                                // 10^9+7
constexpr i64 inf = 9000000000000000000;                       // 9*10^18
/* macros */
#define MAX(c)        *max_element(ALL(c))
#define MIN(c)        *min_element(ALL(c))
#define SIZE(c)       (i64)((c).size())                        // unsined int (size_t) -> int64_t
#define ALL(c)        (c).begin(), (c).end()
#define RALL(c)       (c).rbegin(), (c).rend()
#define REP(i, n)     for (i64 i=0; i<(i64)(n); ++i)           // 0 to n-1
#define REPD(i, n)    for (i64 i=(i64)(n)-1; i>=0; --i)        // n-1 to 0
/* debug */
#define debug(x)      cerr << #x << ": " << (x) << '\n'
#define debugvec(v)   for (size_t _ = 0; _ < (v).size(); ++_) {cerr << #v << '[' << _ << "]: " << (v)[_] << '\n';}
/* useful output */
auto print = [](auto x) {cout << (x) << '\n';};
template <class T> void printvec(T v, string sep=" ", string end="\n") {REP(i, SIZE(v)-1) cout << v[i] << sep; cout << v[SIZE(v)-1] << end;}
/* useful input */
VS splitstr(string s, char delim=' ') {VS v; string buf; stringstream ss{s}; while (getline(ss, buf, delim)) v.push_back(buf); return v;}




void Main() {
    i32 h, w;
    cin >> h >> w;
    REP(i, h) {
        REP(j, w) {
            string s;
            cin >> s;
            if (s == "snuke") {
                cout << (char)('A' + j);
                cout << i + 1;
                cout << endl;
            }
        }
    }

}


signed main() {
    cin.tie(nullptr);                                         // cin と cout の tie を切り高速化
    cout << fixed << setprecision(15);                        // 浮動小数点数が 1e-006 のように表示されることを防ぐ
    Main();
}

Measured memory_bytes: 3632
#! /usr/bin/env python3

import math

x = int(input())

if x < 4:
    print(1)
else:
    p_max = int(math.sqrt(x))
    res = 0

    for n in range(2, p_max + 1, 1):
        tmp = n
        while tmp * n <= x:
            tmp = tmp * n
            if tmp > res:
                res = tmp

    print(res)


Measured memory_bytes: 2940
w,h,n = map(int,input().split())
c = [list(map(int,input().split())) for i in range(n)]
xmin = 0
xmax = w 
ymin = 0
ymax = h
for i in c:
    if i[2]==1:
        xmin = max(xmin,i[0])
    elif i[2]==2:
        xmax = min(xmax,i[0])
    elif i[2]==3:
        ymin = max(ymin,i[1])
    elif i[2]==4:
        ymax = min(ymax,i[1])
if xmax>xmin and ymax>ymin:
    print((xmax-xmin)*(ymax-ymin))
else:
    print(0)

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

int dp[110][4][4];
int N,M;

int pas[110];

int main(){
		 
	
  cin >> N >> M;
  memset(pas,0,sizeof(pas));	 
  memset(dp,0,sizeof(dp));

  for(int i = 0; i < M; i++){
    int x,y;
    cin >> x >> y;
    pas[x] = y;
  }

  if(pas[1] == 0){
    for(int j = 0; j <= 3; j++){
      dp[1][j][1] = 1;
    }
  }
  else{
    dp[1][pas[1]][1] = 1;
  }


  for(int i = 2; i <= N; i++){
 
    if(pas[i] == 0){ //その日が決まってないなら
      for(int j = 1; j <= 3; j++){
	// k = 2
	if(pas[i+1] == j) //次の日が決まっててアウト
	  dp[i][j][2] = 0;
	else{
	  dp[i][j][2] += dp[i-1][j][1];
	  dp[i][j][2] %= 10000;
	}
	// k = 1
	for(int t = 1; t <= 3; t++){
	  if(j != t){
	    dp[i][j][1] += dp[i-1][t][1] + dp[i-1][t][2];
	    dp[i][j][1] %= 10000;
	  }
	}
 
	//	if( j == pas[i+1] && j == pas[i+2]) dp[i][j][1] = 0;	
      }
    }
    
    if(pas[i] != 0){ //決まってる
      for(int j = 1; j <= 3; j++){
	if(pas[i] != j){
	  dp[i][pas[i]][1] += dp[i-1][j][1] + dp[i-1][j][2];
	  dp[i][pas[i]][1] %= 10000;
	}
      }

      dp[i][pas[i]][2] += dp[i-1][pas[i]][1];
      dp[i][pas[i]][2] %= 10000;	   
	
    }
    for(int j = 1; j <=3 ;j++){
      for(int k = 1; k <= 2; k++){
	//	cout << dp[i][j][k] << " ";
      }
      //      cout << endl;
    }
    //    cout << endl;
  }



  int ans=0;
  for(int j =1; j <= 3;j++){
    for(int k = 1; k <=2 ;k++){
      ans += dp[N][j][k];
      ans %= 10000;
    }
  }
  cout << ans << endl;

  
  return 0;
}

Measured memory_bytes: 1172
#include<cstdio>
#include<iostream>
#include<map>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
char s1[20][20],s2[20][20];
int main(){
	int a,b,flag;
	cin >> a >> b;
	for(int i = 1;i <= a;i++){
		for(int j = 1;j <= a;j++){
			scanf(" %c",&s1[i][j]);
			}
		}
	for(int i = 1;i <= b;i++){
		for(int j = 1;j <= b;j++){
			scanf(" %c",&s2[i][j]);
			}
		}
	for(int i = 1;i <= a - b + 1;i++){
		for(int j = 1;j <= a - b + 1;j++){
			flag = 0;
			for(int k = 1;k <= b;k++){
				for(int l = 1;l <= b;l++){
					if(s1[i+k-1][j+l-1]==s2[k][l]){
						flag++;
						}
					}
				}
				if(flag==b*b)break;
			}
			if(flag==b*b)break;
		}
		if(flag==b*b)puts("Yes");
		else puts("No");
	return 0;
	}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Main{
	public static void main(String[] args){
	int h =0;
	int w =0;
	int t =0;
	Scanner scan = new Scanner(System.in);
	ArrayList<Integer> listw = new ArrayList<Integer>();
	ArrayList<Integer> listh = new ArrayList<Integer>();
		while(scan.hasNextLine()){
			h = scan.nextInt();			
			w = scan.nextInt();
			
			if(h==0 && w==0){
				break;
			}
			else{
				listh.add(h);
				listw.add(w);
			}
		}
		
		
		
		for(int i=0;i<listh.size();i++){
			for(int ii=0;ii<listh.get(i);ii++){
				for(int iii=0;iii<listw.get(i);iii++){
					if(ii%2 == 0){
							if(iii%2 == 0){
								System.out.print("#");
							}
							else{
								System.out.print(".");
							}
					}
					else{
							if(iii%2 == 0){
								System.out.print(".");
							}
							else{
								System.out.print("#");
							}
					}
				}
			System.out.println("");
			}
		System.out.println("");
		}
	}
}

Measured memory_bytes: 34980
import java.util.*;
import java.util.Arrays;
 
class Main {
 
    private static Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
    	long[] t = new long[3];
  		t[0] =Long.parseLong(sc.next());
  		t[1] =Long.parseLong(sc.next());
  		t[2] =Long.parseLong(sc.next());
  		Arrays.sort(t);
  		if(t[0]%2==1 && t[1]%2==1 && t[2]%2==1){
  			System.out.println(t[0]*t[1]);
  		}else{
  			System.out.println(0);
  		}
 
    }
}

Measured memory_bytes: 22612
import numpy as np
N=int(input())
s=input()
west=[]
east=[]
for i in range(N):
    west.append(0)
    east.append(0)
    if(s[i]=='W'):
        west[i]=1
    else:
        east[i]=1
eastsum=np.zeros(N)
westsum=np.zeros(N)
westsum[0]=west[0]
eastsum[N-1]=east[N-1]
for i in range(1,N):
    eastsum[N-1-i]=eastsum[N-i]+east[N-1-i]
    westsum[i]=westsum[i-1]+west[i]
print(int(np.min(eastsum+westsum))-1)

Measured memory_bytes: 24968
#include<stdio.h>
int main(void)
{
        int a,b,c,k,n,m,i;
        scanf("%d%d%d%d",&a,&b,&c,&k);
        if((a>=b)&&(a>=c)) n=a;
        else if(b>=c) n=b;
        else n=c;
        m=n;
        for(i=0;i<k;i++) m+=m;
        printf("%d\n",a+b+c-n+m);
        return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int adiv = (int)Math.floor(a/(double)k);
        int bdiv = (int)Math.floor(b/(double)k);
        int amod = a%k;
        int bmod = b%k;
        System.out.println(adiv<bdiv || amod==0 || bmod==0 ? "OK" : "NG");
    }
}


Measured memory_bytes: 35888
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		int[] map = new int[1000000];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
			if (a[i] > N + 1) continue;
			map[a[i] + N - i]++;
		}
		long ans = 0;
		for (int i = 0; i < N; i++) {
			if (N - a[i] - i >= 0 && N - a[i] - i < 1000000) {
				ans += map[N - a[i] - i];
			}
			if (a[i] <= N + 1) {
				map[a[i] + N - i]--;
			}
		}
		System.out.println(ans);
	}
}


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

int main()
{
  const int mod = 1000000007;
  int n, patterns = 1, prev = 0;
  cin >> n;
  vector<int> p(200001);
  for (int i = 0; i < n; i++) {
    int c, w;
    cin >> c;
    if (c == prev) continue;
    w = (patterns + p.at(c)) % mod;
    patterns = w;
    p.at(c) = w;
    prev = c;
  }
  cout << patterns << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)


int main(){
    int a, b, c; cin >> a >> b >> c;
    if(a + b + 1 >= c) cout << b + c << endl;
    else cout << b + ( a + b + 1) << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    typedef long long ll;
    const int N=200005;
    int n;
    ll a[N];
    using namespace std;
     
    int main()
    {
    	#ifdef Kay
    		freopen ("code.in","r",stdin);
    		freopen ("code.out","w",stdout);
    	#endif
    	cin>>n;
    	int i;
    	for (i=1;i<=n;i++)
    	scanf ("%lld",&a[i]),a[i]-=i;
    	sort(a+1,a+1+n);
    	ll ans=0,val=a[n/2+1];
    	for (i=1;i<=n;i++)
    	if (a[i]<val) ans+=val-a[i];
    	else ans+=a[i]-val;
    	printf ("%lld",ans);
    	return 0;
    }

Measured memory_bytes: 1792
#include <algorithm>
#include <iostream>
#include <queue>
#define N_MAX 30
#define INF (1e9)
using namespace std;
void dijkstra();
int w,h,data[N_MAX][N_MAX],d[N_MAX][N_MAX][4],c[4];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
typedef struct stu{
  int mincost,y,x,dir;
  bool operator<(const stu & right)const{
    return mincost>right.mincost;
  }
} dat;

int main(){
  while(1){
    cin>>w>>h;
    if(!w&&!h) break;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++) cin>>data[i][j];
    for(int i=0;i<4;i++) cin>>c[i];
    dijkstra();
  }
  return 0;
}

void dijkstra(){
  priority_queue<dat > Q;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      for(int k=0;k<4;k++) d[i][j][k]=INF;
  d[0][0][1]=0;
  Q.push((dat){0,0,0,1});
  while(!Q.empty()){
    dat t=Q.top(); Q.pop();
    int cost=t.mincost,y=t.y,x=t.x,dir=t.dir;
    if(cost>d[y][x][dir]) continue;
    for(int i=0;i<4;i++){
      int ny=y+dy[(dir+i)%4],nx=x+dx[(dir+i)%4];
      int ndir=(dir+i)%4;
      if(ny<0||nx<0||h<=ny||w<=nx) continue;
      if(d[ny][nx][ndir]>cost+c[i]){
	d[ny][nx][ndir]=cost+c[i];
	Q.push((dat){d[ny][nx][ndir],ny,nx,ndir});
      }
      if(data[y][x]!=i) continue;
      if(d[ny][nx][ndir]>cost){
	d[ny][nx][ndir]=cost;
	Q.push((dat){d[ny][nx][ndir],ny,nx,ndir});
      }
    }
  }
  int mincost=INF;
  for(int i=0;i<4;i++)
    mincost=min(mincost,d[h-1][w-1][i]);
  cout<<mincost<<endl;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
ll MOD = 1e9+7;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }

int main(){
  ll i, j;
  ll n;
  cin >> n;
  for(i = n; i < 1000; i++){
    if(i == 111 || i == 222 || i == 333 || i == 444 || i == 555 ||
       i == 999 || i == 888 || i == 777 || i == 666 )
      break;
  }
        
  cout << i << endl;

  return 0;
}

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

using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');

int main() {
  ll a, b;
  cin >> a >> b;
  cout << (a >= 13 ? b : a >= 6 ? b / 2 : 0) << endl;
}


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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

// ------------------------------------------------------------------------------------------

using pii = pair<int, int>;

int N, M;
int A[111111];
int B[111111];
int C[111111];
vec<pii> D;

signed main() {
	cin >> N >> M;
	rep (i, N) {
		cin >> A[i];
	}
	rep (i, M) {
		cin >> B[i] >> C[i];
		D.push_back({C[i], B[i]}); // 数値, 回数
	}
	// int t = accumulate(A, A+N, 0ll);

	sort(A, A+N);
	sort(all(D)); reverse(all(D));
	// print1(A, A+N);

	int idx = 0;
	rep (i, M) {
		int lim = D[i].second;
		int val = D[i].first;
		if (A[idx] > val) break;
		if (idx >= N) break;
		rep (j, lim) {
			if (idx >= N) break;
			if (A[idx] > val) break;
			A[idx] = val;
			idx++;
		}
	}

	int ans = 0;
	rep (i, N) {
		ans += A[i];
	}
	// print1(A, A+N);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4336
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> Pi;
typedef queue<Pi> QPi;
typedef pair<ll, ll> Pll;
typedef queue<Pll> QPll;
typedef vector<vi> Graph;
const int mod = 1000000007;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 順列　do {} while(next_permutation(ALL(X)));
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main() {
  char s[100001];
  cin >> s;
  int n=strlen(s);
  int r=0,b=0;
  REP(i,n) {
    if(s[i]=='0') r++;
    if(s[i]=='1') b++;
  }
  int ans=2*min(r,b);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  int n;
  while (cin >> n, n) {
    vi v(86400);
    rep(i, n) {
      int h, m, d;
      char gomi;
      cin >> h >> gomi >> m >> gomi >> d;
      int l = h * 3600 + m * 60 + d;
      cin >> h >> gomi >> m >> gomi >> d;
      int r = h * 3600 + m * 60 + d;
      v[l]++;
      v[r]--;
    }
    loop(i, 1, 86400) v[i] += v[i - 1];
    int c = 0;
    rep(i, 86400) cmax(c, v[i]);
    cout << c << endl;
  }
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
int n,m,head[10001],f[10001],x,y,kl,a[10001];
struct line{int next,to;}q[1000001];
void pushline(int x,int y)
{
	q[++kl].next=head[x];head[x]=kl;q[kl].to=y;
}
inline void dfs(int x,int fa)
{
    f[x]=0;
    for (int p=head[x];int v=q[p].to;p=q[p].next) 
	{
        if(v==fa||a[v]>=a[x])continue;
        dfs(v,x);
		if (!f[v])f[x]=1;
    }
}
signed main() 
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		pushline(x,y);pushline(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		dfs(i,0);
		if(f[i])cout<<i<<" "; 
	}
	
}
/*
直接考虑一条边，假装当前点的石头少，如果我推过去的话就亏大发了，因为对手可以推回来，然后死循环
最后直接没了
因此可以给边定向，拉向小的位置。 
这样直接成个DAG了，拓排之后倒着扫可以直接做完。 
如果有相等 怎么办 
删掉边。然后统一按照必败点处理 
考虑DAG上一个终止节点，它应该是必胜的 
*/

Measured memory_bytes: 3728
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i< int (n); i++)
using namespace std;
typedef long long ll;

int main(){

int n, m;
cin >> n >> m;
int h[1000000]={0};
rep(i,n) cin >> h[i+1];
int good[1000000]={0};
for(int i=1; i<=m; i++) {
    int a, b;
    cin >> a >> b;
    if(h[a]<=h[b]) good[a]++;
    if(h[b]<=h[a]) good[b]++;
}
int ans=0;
for(int i=1; i<=n; i++){
    if(good[i]==0) ans++;
}

cout << ans << endl;

}

Measured memory_bytes: 11460
#include <iostream>
#include <stdio.h>
#include <vector>
#include<algorithm>
using namespace std;

int main()
{
	long  N,K, i, t = 0;
	long  A[200000];

	cin >> N >> K;

	for (auto i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A, A + N);

	for (i = 0; i < N - K; i++){
		t = t + A[i];



	}


	cout << t;

}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
using namespace std;
ll n,t;
ll x,y,d,a,b;
void euclid(ll A,ll B){
   if(B==0)d=A,x=1,y=0;
   else{
    euclid(B,A%B);
    ll temp=x;
    x=y;
    y=(temp-(A/B)*y);
   }
}
ll inverse(ll x1){
  euclid(x1,M);
  return (x%M+M)%M;
}
ll powermod(ll x,ll n)
{
    if(n==0)  return 1;
    else if(n%2 == 0)return powermod((x*x)%M,n/2);
    else return (x*powermod((x*x)%M,(n-1)/2))%M;
}
int main(){
      ios_base::sync_with_stdio(false); cin.tie(NULL);
      cin>>n>>a>>b;
      ll sum1=1,sum2=1,ans1=1,ans2=1;
      for(int i=1;i<=a;i++)
      {
        ans1=(ans1*(n-i+1))%M;
        sum1=(sum1*inverse(i))%M;
      }
      for(int i=1;i<=b;i++)
      {
        ans2=(ans2*(n-i+1))%M;
        sum2=(sum2*inverse(i))%M;
      }
      ans1=(ans1*sum1)%M;
      ans2=(ans2*sum2)%M;
      ll ans=(powermod(2ll,n)-ans1+M)%M;
      cout<<(ans-ans2+M)%M-1;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int n,m,x,y,xpos[105],ypos[105];
  bool xflg,yflg;
  cin>>n>>m>>x>>y;
  for(int i=0;i<n;i++){
    cin>>xpos[i];
  }
  for(int i=0;i<m;i++){
    cin>>ypos[i];
  }
  for(int z=x+1;z<=y;z++){
    xflg=false;
    yflg=false;
    for(int i=0;i<n;i++){
      if(z<=xpos[i]) break;
      if(i==n-1) xflg=true;
    }
    for(int i=0;i<m;i++){
      if(z>ypos[i]) break;
      if(i==m-1) yflg=true;
    }
    if(xflg&&yflg){
      printf("No War\n");
      break;
    }
  }
  
  if(!xflg||!yflg) printf("War\n");
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>

using namespace std;

int main() {
	int a[4]{0}, n;
	string s;
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; i++) {
		if (s[i] == 'N')
			a[0] = 1;
		if (s[i] == 'W')
			a[1] = 1;
		if (s[i] == 'S')
			a[2] = 1;
		if (s[i] == 'E')
			a[3] = 1;
	}
	if (a[0] ^ a[2] || a[1] ^ a[3])cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(){
  int a,b,c,x;
  double m;
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&x);
  c=a*a*b;
  if(c<(x<<1)){
    m=atan((double)(c-x)*2/(a*a*a));
    m*=180;
    m/=M_PI;
    printf("%.7f",(double)m);
  }else{
    m=atan(((double)x*2)/(a*b*b));
    m*=180;
    m/=M_PI;
    printf("%.7f",(double)90.0-m);
  }
  return(0);
}

Measured memory_bytes: 128
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N+1):
    v = i
    score = 0
    size = 0
    while True:
        size += 1
        score += C[v]
        if i == P[v]:
            break
        v = P[v]

    if score > 0:
        tmp = score*(K//size-1)
        num = K%size+size
    else:
        tmp = 0
        num = min(K, size)
    
    v = i
    for _ in range(num):
        tmp += C[v]
        v = P[v]
        ans = max(tmp, ans)

print(ans)

Measured memory_bytes: 73880
N, A, B, C, D = map(int, input().split())
S = input()

if C < D:
    answer = 'Yes'
    prev = ''
    for s in S[A-1:C]:
        if prev == s and s == '#':
            answer = 'No'
        prev = s
    prev = ''
    for s in S[B-1:D]:
        if prev == s and s == '#':
            answer = 'No'
        prev = s
    print(answer)
else:
    answer = 'No'
    for i in range(B-1, D):
        if S[i-1] == '.' and S[i] == '.' and S[i+1] == '.':
            answer = 'Yes'
    prev = ''
    for s in S[A-1:C]:
        if prev == s and s == '#':
            answer = 'No'
        prev = s
    print(answer)

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using namespace std;

const int N = 3e6;
int n, a[N];

int main() {
#ifdef LC
	//assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	n *= 2;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(a, a + n);
	ll ans = 0;
	for (int i = 0; i < n; i += 2) {
		ans += a[i];
	}
	cout << ans << "\n"; 
	return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = Integer.parseInt(sc.next());
		long ret = 0;
		int i = 2;
		while (true) {
			int step = i / 2;
			long start = (i + 1) / 2 * step;
			if (start > N)
				break;
			long end = N / step * step;
			ret += (start + end) * ((end - start) / step + 1) / 2;
			i += 1;
		}
		System.out.println(ret);
	}
}

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

int main()
{
  int N;
  cin >> N;
  
  vector<int> A(N), B(N), C(N-1);
  int ans = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
    cin >> B.at(i);
  }
  for (int i = 0; i < N-1; i++) {
    cin >> C.at(i);
  }
  
  for (int i = 0; i < N; i++) {
    ans += B.at(A.at(i)-1);
  }
  for (int i = 1; i < N; i++) {
    if (A.at(i - 1) + 1 == A.at(i)) {
      ans += C.at(A.at(i - 1)-1);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pf(n) printf("%d\n",n)
#define pff(a,b) printf("%d  %d\n",a,b);
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int k;
	cin >> k;
	bool ok = true;
	while (a >= b) {
		if (k == 0) {
			ok = false;
			break;
		}
		b *= 2;
		k--;
		//pff(b, k);
	}
	while (b >= c) {
		if (k == 0) {
			ok = false;
			break;
		}
		c *= 2;
		k--;
	}
	if (ok) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}

	return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n, a, sum = 0, num = 2001; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> a; sum = max(sum, a); num = min(num, a);
	}
	cout << max(sum - (abs(sum - num) / 2 + min(sum, num)), num - (abs(sum - num) / 2 + min(sum, num))) << endl;
	cin >> n;
}


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

#define ms(s, n) memset(s, n, sizeof(s))
#define f(i, a, b) for (int i = (a); i <=(b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<ll> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int MOD2 = MOD + 2; //1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) - 1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
int modulo(int a, int b) { return (a % b + b) % b; }
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

/*
class Compare
{
  public:
    bool operator()(pi a,pi b)
    {
      if(a.first<b.first || (a.first==b.first && a.second>b.second))
        return true;
      return false;
    }
};
*/

int main()
{
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n;
	cin >> n;
	unordered_map<string, ll>freq;
	f(i, 0, n - 1) {
		string s;
		cin >> s;
		freq[s]++;
	}
	cout << "AC x " << freq["AC"] << endl;
	cout << "WA x " << freq["WA"] << endl;
	cout << "TLE x " << freq["TLE"] << endl;
	cout << "RE x " << freq["RE"] << endl;
	// read the stuff at the bottom
	return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/





























Measured memory_bytes: 3668
#include <bits/stdc++.h>
        using namespace std;
        #define int long long int
        #define pb push_back
        #define mk make_pair
        #define ft first
        #define sc second
        #define ppb pop_back
        #define sz size
        #define forn(i,a,n) for(i=a;i<n;i++)
        #define M 998244353 
        #define inf 2e18

        signed main() {
 

        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        
        int n;
        cin>>n;
        n=n%10;
        if(n==3)
            cout<<"bon\n";
        else if(n==0||n==1||n==6|n==8)
            cout<<"pon\n";
        else
            cout<<"hon\n";


        return 0;
    }

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define PN printf("\n")
#define MODV 1000000007

typedef long long ll;
typedef double dbl;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
void addmod(int &a, ll b){a=(a+b); if(a>=MODV)a-=MODV;}
void mulmod(int &a, ll b){a=(a*b)%MODV;}
template<class T>bool domin(T &a, const T &b){return a>b?a=b,1:0;}
template<class T>bool domax(T &a, const T &b){return a<b?a=b,1:0;}
int gi(){int a;scanf("%d",&a);return a;}
ll gll(){ll a;scanf("%lld",&a);return a;}
class graphal
{
  public:
    int n;
    //1 1->bidirectional, 2->reverse edges
    vector<vi> ed;
    vi sz, dp, p;
    graphal(const int &n):n(n),ed(n),sz(n,0),dp(n,0),p(n,-1){}
    void reset(int n){
    ed.clear();
    this->n=n;
    ed.resize(n);
  }
    void add(int a, int b){ ed[a].push_back(b);ed[b].push_back(a); }
    void load(int m){ for(int i=0;i<m;i++){int a=gi(),b=gi();add(a-1,b-1);}}
    void dfs(int v=0, int pa=-1, int d=0){
      sz[v]=1;
      dp[v]=d;
      p[v]=pa;
      for(auto i:ed[v])
        if(i!=pa){
          dfs(i,v,d+1);
          sz[v]+=sz[i];
        }
    }
    void doit() {
      int d=(dp[n-1]-1)/2;
      int cn=n-1;
      for(int i=0;i<d;i++){
        cn=p[cn];
      }
      int sza=n-sz[cn], szb=sz[cn];
      if(szb>=sza)cout<<"Snuke"<<endl;
      else cout<<"Fennec"<<endl;
    }
};

int main() {
  int n=gi();
  graphal g(n);
  g.load(n-1);
  g.dfs();
  g.doit();
  return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

typedef tuple<ll,int,int> elem;

const int MAX_N = 100000;
int n;
ll x;
ll b[MAX_N];
ll l[MAX_N];
ll u[MAX_N];
pli total[MAX_N];
ll d;

bool check(ll y) {
  ll q = y/x;
  ll r = y - q*x;

  ll s = accumulate(total,total+q,0LL,[](ll a, pli p2) { return a + p2.fst; });

  ll res = 0;
  forn(i,n) {
    int j = total[i].snd;

    if (i < q) {
      s -= total[i].fst;
      s += total[q].fst;
    }

    ll lc = min(r,b[j]);

    chmax(res, s + l[j]*lc + u[j]*(r-lc));

    if (i < q) {
      s += total[i].fst;
      s -= total[q].fst;
    }
  }

  return res + d >= 0;
}

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  ll r = 0;
  cin >> n >> x;
  forn(i,n) {
    cin >> b[i] >> l[i] >> u[i];
    d -= l[i] * b[i];
    r += b[i];
  }

  forn(i,n) {
    total[i].fst = b[i]*l[i] + (x-b[i])*u[i];
    total[i].snd = i;
  }

  sort(total,total+n,greater<pli>());

  ll l = -1;
  while (r - l > 1) {
    ll mid = l + (r - l) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid;
  }

  cout << r << endl;

  return 0;
}


Measured memory_bytes: 4096
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String str = br.readLine();
			int N = Integer.parseInt(str);
			str = br.readLine();
			String[] s = str.split(" ",0);
			int max = 0;
			int min = 0;
			for(int i = 0;i < N; i++) {
				int a = Integer.parseInt(s[i]);
				if(i == 0) {
					max = a;
					min = a;
				}
				if(max < a) max = a;
				if(min > a) min = a;
			}
			System.out.println(max-min);
//			long max  = 1000000007;
		}catch (Exception e) {
			System.exit(0);
		}
	}
}


Measured memory_bytes: 20308
#include <bits/stdc++.h>  
 
using namespace std;
 
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define FORr(i, j, k) for(int i = j; i >= k; --i)
#define repr(i, j) FOR(i, j, 0)
#define gcd(x, y) int gcd(int x, int y) {return (y == 0) ? x : gcd(y, x % y);}
#define INF (1 << 30)
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
 
const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};
 
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
 
int dp[3][1000001];
 
int main() {
    string s;
    cin >> s;
    dp[0][0] = dp[1][0] = dp[2][0] = 0;
    int res = 0;
    rep(i, s.size()) {
        if(s[i] == 'J') dp[0][i + 1] = dp[0][i] + 1;
        else if(s[i] == 'O') dp[1][i + 1] = dp[1][i] + 1;
        else {
            dp[2][i + 1] = dp[2][i] + 1;
            if(i + 1 - dp[2][i + 1] * 3 >= 0) {
                if(dp[2][i + 1] == dp[1][i + 1 - dp[2][i + 1]] && dp[2][i + 1] <= dp[0][i + 1 - dp[2][i + 1] * 2]) {
                    res = max(res, dp[2][i + 1]);
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

Measured memory_bytes: 15792
l=set()
s={}
while 1:
    n,k=map(int,raw_input().split(','))
    if n==k==0:
        break
    l.add(k)
    s[n]=k
l2=sorted(list(l))[::-1]
while 1:
    try:
        n=int(raw_input())
        print l2.index(s[n])+1
    except:
        break

Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int N,M;
    cin >> N >> M;
    vector<pair<int,int>> vp(M);
    rep(i,M){
        int a,b;
        cin >> a >> b;
        vp[i]=make_pair(b-1,a-1);
    }
    // bの小さい順にみていく
    sort(vp.begin(),vp.end());
    ll ans = 0;
    ll last_cut = 0;
    rep(i,M){
        if(i!=0){
            if(last_cut<=vp[i].second){
                // b-1とbの間で橋を落とす
                last_cut = vp[i].first;
                ans++;
            }
        }else{
            last_cut = vp[i].first;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4000
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define MOD 1000000007
int main(){
	ll a, cnt=0, ans=0;
	cin>>a;
	ll arr[a];
	for (ll i=0; i<a; i++) cin>>arr[i], cnt+=arr[i];
	for (ll i=0; i<a-1; i++){
		cnt-=arr[i];
		ans+=(arr[i]%MOD)*(cnt%MOD);
		ans%=MOD;
	}
	cout<<ans<<endl;
}
//    ll a, ans=0;
//    cin>>a;
//    ll arr[a+1], ps[a+1];
//    for (ll i=1; i<=a; i++) cin>>arr[i];
//    ps[0]=0;
//    for (ll i=1; i<=a; i++) ps[i]=ps[i-1]+arr[i];
//    for (ll i=1; i<a; i++){
//        ans+=(arr[i]*((ps[a]-ps[i])%MOD))%MOD;
//        ans%=MOD;
//    }
//    cout<<ans<<endl;


Measured memory_bytes: 5224
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const ll inf=1e9+7;
const ll INF=1e18;

const int MAX=510000;

vll fac(MAX);
vll finv(MAX);
vll inv(MAX);

void combinit(ll m){
    fac[0]=1;fac[1]=1;
    finv[0]=1;finv[1]=1;
    inv[1]=1;
    rep2(i,2,MAX){
        fac[i]=fac[i-1]*i%m;
        inv[i]=m-inv[m%i]*(m/i)%m;
        finv[i]=finv[i-1]*inv[i]%m;
    }
}

ll combi(ll n,ll k,ll m){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%m)%m;
}

int main(){
    ll n,k;cin>>n>>k;
    vll ans(k);
    combinit(inf);
    for(ll i=0;i<k;i++)ans[i]=(combi(n-k+1,i+1,inf)*combi(k-1,i,inf))%inf;
    rep(i,k)cout<<ans[i]<<endl;
}

Measured memory_bytes: 12288
#include <iostream>

using namespace std;

int main() {
    int N;
    cin >> N;
    if (N % 2 == 0) {
        // Nが偶数の場合はNが答え
        cout << N << endl;
    } else {
        // Nが奇数の場合は2Nが答え
        cout << N * 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
#include <stdio.h>

#define rep(i,m,n) for(unsigned long long int i=(m);i<(n);++i)
#define rem(i,m,n) for(int i=(m);i>(n);--i)
#define MOD 1000000007

using namespace std;

using ll = long long int;
using std::swap;

vector<int> v;
vector<long long int> vll;
vector<long long int> w;
vector<vector<int>> vec(50,vector<int>(4,0));


int ans = 0;
int MA = 0;
int N, M, Q;

vector<int> vvvf;

int set(int x,int y) {
	if (x == N - 1) {
		rep(i, y, M + 1) {
			vvvf[x] = i;
			rep(j, 0, Q) {
				if (vvvf[vec[j][1]-1] - vvvf[vec[j][0]-1] == vec[j][2]) {
					//cout << "vec[j][1]-1=" << vec[j][1] - 1 << ' ';//
					//cout << "vec[j][0]-1=" << vec[j][0] - 1 << ' ';//
					//cout << "vec[j][2]=" << vec[j][2] << ' ';//
					//cout << "j=" << j << ' ';		//
					//cout << '\n';					//
					vvvf[N] += vec[j][3];
				}
			}
			if (vvvf[N] > MA) MA = vvvf[N];
			//rep(i, 0, N + 1)cout << vvvf[i] << ' ';	//
			//cout << '\n';							//
			vvvf[N] = 0;
		}
		vvvf.resize(N + 1, 0);
		return 0;
	}else {
		rep(i, y, M + 1) {
			vvvf[x] = i;
			//cout << vvvf[x] << ' ';//
			//cout <<"x=" << x << ' ';//
			set(x+1, i);
		}
	}
	return 0;
}

int main() {
	cin >> N >> M >> Q;
	v.resize(N);
	
	rep(i, 0, Q)cin >> vec[i][0] >> vec[i][1] >> vec[i][2] >> vec[i][3];
	//sort(vec.begin(), vec.end(), [](const vector<int> &alpha, const vector<int> &beta) {return alpha[0] < beta[0]; });//
	//cout << '\n';																						//
	//rep(i, 0, Q)cout << vec[i][0] << ' ' << vec[i][1] << ' ' << vec[i][2] << ' ' << vec[i][3] << '\n';	//
	//cout << '\n';																						//
	
	vvvf.resize(N + 1, 0);
	//rep(i, 0, N + 1)cout << vvvf[i] << ' ';
	//cout << '\n';
	
	set(0,1);

	cout << MA << '\n';
	
	return 0;
}

Measured memory_bytes: 3620
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <list>
#include <queue>
#include <iostream>

#define maxn 100005
#define PI 3.14159265
#define debug(a) cout << #a << " = " << a << endl

using namespace std;

string s;

int main() {
  //  freopen("in.inp", "r", stdin);

    cin >> s;
    int res = 0;
    string t = "CODEFESTIVAL2016";
    for(int i = 0; i < s.length(); i++)
        if (s[i] != t[i]) res++;

    cout << res;
}


Measured memory_bytes: 384
using System;

namespace atcoderA
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            string a = input[0];
            string b = input[1];

            if (a == "H")
            {
                Console.WriteLine(b == "H" ? "H" : "D");
            }
            else
            {
                Console.WriteLine(b == "H" ? "D" : "H");
            }
        }
    }
}

Measured memory_bytes: 13140
n = int(input())


def f():
  used = set()
  prev = input()
  used.add(prev)
  for i in range(n-1):
    word = input()

    if word in used:
      return 'No'
    else:
      used.add(word)
    
    if word[0] == prev[-1]:
      prev = word
      continue
    else:
      return 'No'
    
  return 'Yes'

print(f())

Measured memory_bytes: 3060
a,b = map(int,input().split())

if(a > b):
    d = a-b
else:
    d = b-a

if(d%2 == 0):
    if(a > b):
        print(a - int(d/2))
    else:
        print(b - int(d/2))


else:
    print('IMPOSSIBLE')


Measured memory_bytes: 2940