akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

#define M 1046527
#define NLL (-1)
#define L 14
char H[M][L];

int getChar(char ch)
{
    if(ch == 'A')   return 1;
    else if(ch == 'C')  return 2;
    else if(ch == 'G')  return 3;
    else if(ch == 'T')  return 4;
    else   return 0;
}

long long getKey(char str[])
{
    long long sum = 0, p = 1, i;
    for(i = 0; i<strlen(str); i++)
    {
        sum += p*(getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key)    {  return key%M;  }
int h2(int key)    {return 1+(key%(M-1));}

int find(char str[])
{
    long long key, i, h;
    key = getKey(str);
    for(i=0; ; i++)
    {
        h = (h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str) == 0)   return 1;
        else if(strlen(H[h]) == 0)  return 0;
    }
    return 0;
}
int insert(char str[])
{
    long long key, i, h;
    key = getKey(str);
    for(i=0; ; i++)
    {
        h = (h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str) == 0)   return 1;
        else if(strlen(H[h]) == 0)
        {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main()
{
    int i, n, h;
    char str[L], com[9];
    for(i=0; i<M; i++)
        H[i][0] = '\0';
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%s %s", com, str);
        if(com[0] == 'i')
        {
            insert(str);
        }
        else
        {
            if(find(str))
            {
                printf("yes\n");
            }
            else
            {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 17424
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;



int main() {
    ll N, A, B, ans;
    cin >> N >> A >> B;

    if (B > A * N) ans = A * N;
    else ans = B;
    
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,ls[30],mx1,mx2,x,c[30];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=26;i++)scanf("%d",&c[i]),ls[i]=0;
    for(int i=1;i<=n;i++)
    {
        mx1=0,mx2=1;
        for(int j=1;j<=26;j++)
        {
            scanf("%d",&x);
            if(mx1<(i-ls[j])*c[j])mx1=(i-ls[j])*c[j],mx2=j;
            else if(mx1==(i-ls[j])*c[j])if(ls[j]<ls[mx2])mx2=j;
        }
        //printf("[%d]",mx1);
        ls[mx2]=i;
        printf("%d\n",mx2);
    }
}


Measured memory_bytes: 3740
/**
 * ?????????:O(n^2)
 * ??±?????????????¨?????????´??\?????¢??????????????????????´?,?±????????¨???????????????????
 */
#include <stdio.h>

// ????????????,????????????????????¢????¬???°
int selectionSort(int A[], int N){
	int i, j, minj, sw = 0, tmp;
	for(i = 0; i < N-1; i++){
		minj = i;
		for(j = i+1; j < N; j++){ // ?????°????°????
			if(A[minj] > A[j]) minj = j;
		}
		tmp = A[minj]; A[minj] = A[i]; A[i] = tmp;
		if(i != minj) sw++;
	}
	return sw;
}

int main(){
	//freopen("in.txt", "r", stdin);
	int i,N,A[100],sw;
	while(~scanf("%d", &N)) {
	    for(i = 0; i < N; i++) scanf("%d", &A[i]);
           sw = selectionSort(A, N);
           for(i = 0; i < N; i++){
           	if(i > 0) printf(" ");
           	printf("%d", A[i]);
           }
           printf("\n");
           printf("%d\n", sw);
	}
	return 0;
}

Measured memory_bytes: 1860
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(ll i=(a);i<(n);i++)
#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}
template<class S>void tf(bool b,S t,S f){cout<<(b?t:f)<<endl;}
void OUT(bool b){tf(b,"YES","NO");}
void Out(bool b){tf(b,"Yes","No");}
void out(bool b){tf(b,"yes","no");}
template<class T>void puta(T&&t){cout<<t<<endl;}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}

int popcnt(int x){return __builtin_popcount(x);}
int popcnt(ll x){return __builtin_popcountll(x);}
int bsr(int x){return 31 - __builtin_clz(x);}
int bsr(ll x){return 63 - __builtin_clzll(x);}
int bsf(int x){return __builtin_ctz(x);}
int bsf(ll x){return __builtin_ctzll(x);}
template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}

/*他のライブラリを入れる場所*/

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin>>s;
	int n=s.size();
	bool ok=false;
	rep(i,n+1)range(j,i,n+1){
		ok|=(s.substr(0,i)+s.substr(j)=="keyence");
	}
	OUT(ok);
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;

int main() {
    ll n; cin >> n;
    vl a;
    for(ll i = 0; i < n; i++) {
        ll num; 
        std::cin >> num;
        a.push_back(num);
    }
    std::multiset<ll> s;
    for(ll i = 0; i < n; i++) {
        if (s.empty() || s.upper_bound(-a[i]) == s.end()) {
            ;
        } else {
            // std::cerr << "remo" << *s.upper_bound(-a[i]) << std::endl;
            s.erase(s.upper_bound(-a[i]));
        }
        s.insert(-a[i]);
    }
    cout << s.size() << endl;
}


Measured memory_bytes: 5748
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int a[n+1];
	for (int i=1; i<=n; i++) a[i]=-1;
	for (int i=1; i<=m; i++)
	{
		int x, y;
		cin >> x >> y;
		if (a[x]==-1) a[x]=y;
		else if (a[x]!=y)
		{
			cout << -1 << endl;
			return 0; 
		}
	}
	if (a[1]==0&&n!=1)
	{
		cout << -1 << endl;
		return 0;
	}
	if (a[1]==-1&&n!=1) a[1]=1;
	if (a[1]==-1&&n==1) a[1]=0;
	for (int i=1; i<=n; i++)
	{
		if (a[i]==-1) a[i]=0;
		cout << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
long long a[100],n;
using namespace std;
int main()
{
cin>>n;
	a[0]=2,a[1]=1;
	for(long long j=2;j<=n;j++)
	
	a[j]=a[j-1]+a[j-2];
	

cout<<a[n];
	
	
	
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int l, r;
        cin >> l >> r; ans += r - l + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int a,b,c;
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&c);
  
  if(a<=c&&c<=b)
  {
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
  
  return 0;
}
  

Measured memory_bytes: 128
/*
      d888888b                         d888888b
   d888    8888b                    d888888   888b
 d88    88  898888b               d8888  888     88b
d8P        88888888b             d88888888888     b8b
88        8888888888             88888888888       88
88       88888888888             8888888888        88
98b     88888888888P             988888888        d8P
 988     888  8888P      _=_      9888898  88    88P
   9888   888888P      q(-_-)p       98888    888P
      9888888P         '_) (_`         9888888P
         88            /__/  \            88
         88          _(<_   / )_          88
        d88b        (__\_\_|_/__)        d88b
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                                                          
                     saint_coder

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
*/

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define pb push_back 
#define mp make_pair
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORD(i,a,b) for(int i=(a);i>(b);i--)
#define inp(x) cin>>x
#define inp2(a,b) cin>>a>>b
#define inp3(a,b,c) cin>>a>>b>>c
#define print(x) cout<<x<<" "
#define print2(a,b) cout<<a<<" "<<b<<" "
#define print3(a,b,c) cout<<a<<" "<<b<<" "<<c<<" "
#define printl(x) cout<<x<<endl
#define WL(t) while(t --)
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define SZ(x) ((int)(x).size())
#define inrange(i,a,b) ( ( i>=min(a,b) ) && ( i<=max(a,b) ) )


typedef long long ll;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef pair<int,int> pii;

int32_t main(){

	/*int testcases;
	cin>>testcases;

	WL(testcases){
		
		int n;
		cin>>n;

		int a[n];
		FOR(i,n)
			cin>>a[i];		
	}*/	

	int n;
	cin>>n;

	vector<pii> v;

	int t,d;
	FOR(i,0,n){

		inp2(t,d);
	
		v.pb({d,t});
	}
	
	sort(all(v));
	int time=0;
	FOR(i,0,n){
		
		int d = v[i].F;
		int t = v[i].S;
		
		time += t;
		
		if(time>d){
			printl("No");
			return 0;
		}
			
		
	}
	printl("Yes");
	return 0;	
}




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

int main(){
	for(int i = 0; i < 9; ++i) {
		for(int j = 0; j < 9; ++j) {
			cout << i+1 << "x" << j+1 << "=" << (i+1)*(j+1) << endl;
		}
	}
    return 0;
}

Measured memory_bytes: 1116
#include <iostream>

using namespace std;

typedef long long ll;

ll n, A, a[51], dp[55][55][2700]{};

int main() {
	
	cin >> n >> A;
	for (int i = 0; i < n; i++)cin >> a[i];
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= 2600; k++) {
				if (k - a[i] >= 0)dp[i + 1][j + 1][k] += dp[i][j][k-a[i]];
				dp[i + 1][j][k] += dp[i][j][k];
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 2700; j++) {
			if (j%i == 0 && j / i == A)ans += dp[n][i][j];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 57600
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<string> split(const string &str, char sep)
{
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}

int main() {
    string s;
    cin >> s;
    vector<string> v = split(s, '/');
    int year = atoi(v[0].c_str());
    int month = atoi(v[1].c_str());
    int day = atoi(v[2].c_str());
    if(year < 2019) {
        cout << "Heisei" << endl;
        return 0;
    }
    if(year == 2019 && month <= 4 && day <= 30) {
        cout << "Heisei" << endl;
        return 0;
    }
    cout << "TBD" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define RREP(i, n) for(int i = n; i >= n; i--)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define INF 2000000000	//int型は2 * 10^9ぐらいまで
#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

signed main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string a, b;
	cin >> a >> b;

	if(a.size() > b.size())	cout << "GREATER" << endl;
	elif(a.size() < b.size()) cout << "LESS" << endl;
	elif(a > b) cout << "GREATER" << endl;
	elif(a < b) cout << "LESS" << endl;
	else cout << "EQUAL" << endl;

	rtn 0;
}

Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//The Enemy of My Enemy is My Friend
public class Main{

	Map<String, Integer> ref;
	int ID;
	int reg(String s){
		if(ref.containsKey(s))return ref.get(s);
		ref.put(s, ID);
		return ID++;
	}
	
	int N, res;
	int[] sum, B;
	long[] adj;
	
	void f(int k, int score, long mask){
		res = Math.max(res, score);
		if(k==N)return;
		if(score+sum[k]<=res)return;
		if(((mask>>k)&1)==0)f(k+1, score+B[k], mask|adj[k]);
		f(k+1, score, mask);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			N = sc.nextInt();
			if(N==0)break;
			ref = new HashMap<String, Integer>();
			ID = 0;
			adj = new long[N];
			B = new int[N];
			for(int i=0;i<N;i++){
				int id = reg(sc.next());
				B[id] = sc.nextInt();
				int m = sc.nextInt();
				while(m--!=0)adj[id]+=1L<<reg(sc.next());
			}
			sum = new int[N+1];
			for(int i=N-1;i>=0;i--)sum[i]=sum[i+1]+B[i];
			res = 0;
			f(1, B[0], adj[0]);
			System.out.println(res);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

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

int main() {
	// your code goes here
	int n;
	cin >> n;
	// dp[i] = Probability that there are i heads so far
	vector<double> dp(n+1, 0);
	dp[0] = 1;
	for(int i = 1; i <= n; ++i) {
	    double p_heads;
	    cin >> p_heads;
	    for(int j = i; j >= 0; --j) {
	        dp[j] = (j == 0 ? 0 : dp[j-1] * p_heads) + dp[j] * (1 - p_heads);   
	    }
	}
	double ans = 0;
	for(int i = n/2+1; i <= n; ++i) {
	    ans += dp[i];
	}
	cout << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
  int m,f,r;
  for(int i=0; i<50; i++) {
      cin >> m >> f >> r;
      if(m==-1&&f==-1&&r==-1) {
          return 0;
      }
      if(m==-1||f==-1) {
          cout << "F" << endl;
      }
      else if(m+f>=80) {
          cout << "A" << endl;
      }
      else if(m+f>=65) {
          cout << "B" << endl;
      }
      else if(m+f>=50) {
          cout << "C" << endl;
      }
      else if(m+f>=30) {
          if(r>=50) {
              cout << "C" << endl;
          }
          else {
              cout << "D" << endl;
          }
      }
      else {
          cout << "F" << endl;
      }
  }
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int n, m;
vector<vector<int> > G;
vector<int> ans;
queue<int> que;
void solve(int u){
    for (const auto &x : G[u]){
        if (ans[x]!=-1) continue;
        ans[x] = u+1;
        que.push(x);
    }
}

int main(){
    int a, b, z;
    sc(n), sc(m);
    G.resize(n), ans.resize(n,-1);
    rep(i, 0, m){
        sc(a), sc(b), a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ans[0] = 0;
    rep(i, 0, G[0].size()){
        ans[G[0][i]] = 1;
        que.push(G[0][i]);
    }
    while(!que.empty()){
        z = que.front(); que.pop();
        solve(z);
    }
    bool check = true;
    rep(i, 0, n) if (ans[i]==-1) check = false;
    if (!check) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        rep(i, 1, n) cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 10336
s = input().strip()

answ, ansb = 0, 0
prevw, prevb = '1', '0'
for _s in s:
  if prevw == '1':
    if _s == '1':
      answ += 1
    prevw = '0'
  elif prevw == '0':
    if _s == '0':
      answ += 1
    prevw = '1'
  if prevb == '1':
    if _s == '1':
      ansb += 1
    prevb = '0'
  elif prevb == '0':
    if _s == '0':
      ansb += 1
    prevb = '1'

print(min(answ, ansb))


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

typedef long long ll;
typedef pair<ll,ll> P;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);

	ll n, m;cin >> n >> m;
	vector<P> v(n);REP(i, n)cin >> v[i].FI >> v[i].SE;
	sort(ALL(v));
	priority_queue<ll> pq;
	ll ans = 0;
	ll place = 0;

	for(int day = 1;day <= m;day++){
		while(place < n && v[place].FI <= day){
			pq.push(v[place].SE);
			place++;
		}
		if(!pq.empty()){
			ans += pq.top();
			pq.pop();
		}
	}

	cout << ans << endl;

	return 0;
}


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

int main () {
  long long N, A, B ;
  cin >> N >> A >> B;
  long long X, Y ;
  X = N / (A+B);
  Y = N % (A+B);
  if(Y>A) Y = A ;
  cout << X * A + Y << endl ; 
}

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

#define int long long

signed main() {
  vector<char> ca;
  vector<int> la;
  {
    char c;
    while ( cin >> c, c != '$' ) {
      int l;
      cin >> l;
      ca.emplace_back(c);
      la.emplace_back(l);      
    }
  }

  vector<char> cb;
  vector<int> lb;
  {
    char c;
    while ( cin >> c, c != '$' ) {
      int l;
      cin >> l;
      cb.emplace_back(c);
      lb.emplace_back(l);      
    }
  }

  vector<char> cc;
  vector<int> lc;
  {
    char c;
    while ( cin >> c, c != '$' ) {
      int l;
      cin >> l;
      cc.emplace_back(c);
      lc.emplace_back(l);      
    }
  }

  int a = ca.size(), b = cb.size(), c = cc.size();
  vector<char> ansc;
  vector<int> ansl;  
  for ( int i = 0; i < a; i++ ) {
    if ( ca[i] != cb[0] || la[i] < lb[0] ) continue;
    if ( i+b > a ) continue;
    if ( ca[i+b-1] != cb[b-1] ||la[i+b-1] < lb[b-1] ) continue;
    bool flag = true;
    for ( int j = 1; j < b-1; j++ ) {
      if ( ca[i+j] != cb[j] ||la[i+j] != lb[j] ) {
	flag = false;
	break;
      }
    }

    if ( flag ) {
      if ( b == 1 ) {
	for ( int j = 0; j < i; j++ ) {
	  // cout << ca[j] << " " << la[j] << " ";
	  ansc.emplace_back(ca[j]);
	  ansl.emplace_back(la[j]);
	}
	for ( int j = 0; j < c; j++ ) {
	  // cout << cc[i] << " " << lc[j] << " ";
	  ansc.emplace_back(cc[j]);
	  ansl.emplace_back(lc[j]);
	}
	if ( la[i]-lb[0] >= 1 ) {
	  ansc.emplace_back(ca[i]);
	  ansl.emplace_back(la[i]-lb[0]);
	}
	for ( int j = i+b; j < a; j++ ) {
	  // cout << ca[j] << " " << la[j] << " ";
	  ansc.emplace_back(ca[j]);
	  ansl.emplace_back(la[j]);	
	}
	break;  
      } else {
	for ( int j = 0; j < i; j++ ) {
	  // cout << ca[j] << " " << la[j] << " ";
	  ansc.emplace_back(ca[j]);
	  ansl.emplace_back(la[j]);
	}
	// cout << ca[i] << " " << la[i]-lb[0] << " ";
	if ( la[i]-lb[0] >= 1 ) {
	  ansc.emplace_back(ca[i]);
	  ansl.emplace_back(la[i]-lb[0]);
	}
	for ( int j = 0; j < c; j++ ) {
	  // cout << cc[i] << " " << lc[j] << " ";
	  ansc.emplace_back(cc[j]);
	  ansl.emplace_back(lc[j]);
	}
	// cout << ca[i+b-1] << " " << la[i+b-1]-lb[b-1] << " ";
	if ( b > 1 ) {
	  if ( la[i+b-1]-lb[b-1] >= 1 ) {
	    ansc.emplace_back(ca[i+b-1]);
	    ansl.emplace_back(la[i+b-1]-lb[b-1]);
	  }
	}
	for ( int j = i+b; j < a; j++ ) {
	  // cout << ca[j] << " " << la[j] << " ";
	  ansc.emplace_back(ca[j]);
	  ansl.emplace_back(la[j]);	
	}
	break;      
      }
    }
  }

  if ( ansc.size() == 0 ) {
    ansc = ca; ansl = la;    
  }
  
  for ( int i = 0; i < (int)ansc.size(); i++ ) {
    if ( ansl[i] == 0 ) continue;    
    if ( i < (int)ansc.size()-1 ) {
      if ( ansc[i] == ansc[i+1] ) {
	ansl[i+1] += ansl[i];	
      } else {
	cout << ansc[i] << " " << ansl[i] << " ";	
      }
    } else {
      cout << ansc[i] << " " << ansl[i] << " ";	
    }
  }
  cout << '$' << endl;
  
  return 0;
}



Measured memory_bytes: 3212
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

N = I()

MAX = 10**18
result = 1
A = FLI()
if 0 in A:
    print(0)
    exit()
    
for i in A:
    result *= int(i)
    if result > MAX:
        print(-1)
        exit()

print(result)

Measured memory_bytes: 39984
n=int(input())
l=list(map(int,input().split()))
ans1=0
ans2=0
for i in range(len(l)):
    if l[i]%2==0:
        ans2+=1
    if l[i]%2==1:
        ans1+=1
if  ans1%2==0:
    print('YES')
else:
    print('NO')

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N;
    cin >> N;

    ll minus = 0;
    ll mabs = INF;
    ll total = 0;
    vector<ll> A(N);
    REP(i, N){
        cin >> A[i];
        if(A[i] < 0){
            minus++;
        }
        mabs = min(mabs, abs(A[i]));
        total += abs(A[i]);
    }
    if(minus%2 == 0){
        cout << total << endl;
    }
    else{
        cout << total - 2*mabs << endl;
    }
    



    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;
    OUT((n+1)/2)

    return 0;
}

Measured memory_bytes: 256
widx = []
ridx = []
n = int(input())
s = input()
for i, char in enumerate(s):
  if char == "W":
    widx.append(i)
  else:
    ridx.append(i)
count = 0
i = 0
j = len(ridx) - 1
while i < len(widx) and j >= 0 and widx[i] < ridx[j]:
  i += 1
  j -= 1
  count += 1
print(count)

Measured memory_bytes: 17292
#include <bits/stdc++.h>
 
using namespace std;
 
int scanint() { 
	char c = getchar_unlocked();
	int x = 0;
	for(; (c<48)||(c>57);c = getchar_unlocked());
	for(; (c>47)&&(c<58);c = getchar_unlocked())
		x = 10 * x + c - 48;
    return x;
} 
 
int main() {
 
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    constexpr int A_MAX = 1000000;
 
    vector<int> min_factor(A_MAX);
    // q[n] = i where n = i * p^e, p = min_factor[n], p does not divide i. + 1);
    vector<int> q(A_MAX + 1, 1);
    vector<int> primes;
    for (int i = 2; i <= A_MAX; ++i) {
        min_factor[i] = i;
    }
    for (int i = 2; i <= A_MAX; ++i) {
        if (min_factor[i] == i) {
            primes.push_back(i);
        }
        for (int p : primes) {
            int n = i * p;
            if (n > A_MAX) {
                break;
            }
            min_factor[n] = p;
            if (p == min_factor[i]) {
                q[n] = q[i];
                break;
            } else {
                q[n] = i;
            }
        }
    }
 
    int N = scanint();
    vector<int> a(A_MAX + 1);
    for (int i = 0; i < N; ++i) {
        ++a[scanint()];
    }
 
    bool is_pairwise_coprime = true;
    for (int n = A_MAX; n > 1; --n) {
        if (a[n] > 1) {
            if (a[n] == N) {
                cout << "not coprime" << endl;
                return 0;
            }
            is_pairwise_coprime = false;
        }
        a[min_factor[n]] += a[n];
        a[q[n]] += a[n];
    }
    if (is_pairwise_coprime) {
        cout << "pairwise coprime" << endl;
    } else {
        cout << "setwise coprime" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 15520
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll N;
  cin >> N;
  vll A(N);
  ll ans;
  for(int i = 0; i < N; i++){
    cin >> A.at(i);
    if(A.at(i) == 0){
      cout << 0 << endl;
      return 0;
    }
  }
  for(int i = 0; i < N; i++){
    if(i == 0) ans = A.at(i);
    else{
      ll maxi = 1000000000000000000LL/ans;
      if(A.at(i) > maxi){
        cout << -1 << endl;
        return 0;
      }
      else ans *= A.at(i);
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3992
#include<stdio.h>

void call(int n)
{
  int i, x;
  for(i = 3; i <= n; i++){
    if(i % 3 == 0){
      printf(" %d", i);
    }else{
      x = i;
      do{
        if(x % 10 == 3){
          printf(" %d", i);
          break;
        }
        x /= 10;
      }while(x);
    }
  }
  printf("\n");
}

int main(void)
{
   int n;
   scanf("%d", &n);
   call(n);
  return(0);
}

Measured memory_bytes: 600
from collections import Counter
import itertools
 
N = int(input())
src = [input() for i in range(N)]
 
counter = Counter()
for s in src:
    counter.update(s[0])
    
ans = 0
for pattern in itertools.combinations('MARCH',3):
    a,b,c = pattern
    ans += counter[a] * counter[b] * counter[c]
print(ans)

Measured memory_bytes: 10112
N = int(input())
M = 10**9+7

memo = [{} for _ in range(N+1)] #dict

def ok(last4):
#last4 は 末尾４文字
    for i in range(4):
        t = list(last4)
        if  i >= 1:
            t[i-1],t[i] = t[i],t[i-1]   #入れ替えはこう書ける、覚える
        if "".join(t).count("AGC") >= 1:
            return False
    return True

def dfs(cur, last3):    #深さ優先探索
# cur   は 再帰回数 current?
#last3  は 末尾３文字
    if last3 in memo[cur]:  #memoにlast3が登録されていたら
        return memo[cur][last3] #dictはこれでvalueが出てくる
    if cur == N:    #求める回数再帰したら
        return 1    # ×1 して終了
    ret = 0 #Return(戻り値)の意味か
    for c in "ACGT":
        if ok(last3+c): #禁則事項を破ってないなら
            ret = (ret+dfs(cur+1, last3[1:]+c)) % M
    memo[cur][last3] = ret
    return ret

print(dfs(0,"TTT"))

Measured memory_bytes: 3856
#include <stdio.h>

int main()
{
  int a,b,c;  
    scanf("%d%d%d",&a,&b,&c);
    if(a>b&&b>c) printf("%d %d %d\n",c,b,a);
    else if(a<b&&b<c) printf("%d %d %d\n",a,b,c);
    else if(a>b&&b==c) printf("%d %d %d\n",c,b,a);
    else if(a<b&&a==c) printf("%d %d %d\n",a,c,b);
    else if(a>b&&b<c) printf("%d %d %d\n",b,c,a);
    else printf("????????????????????´");
    
    return 0;
}

Measured memory_bytes: 596
import java.util.*;


public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String s= scanner.nextLine();
    String t= scanner.nextLine();

    int ans = 0;
    for(int i=0; i<s.length(); i++){
      if(s.charAt(i)!= t.charAt(i)){
        ans += 1;
      }
    }
    System.out.println(ans);
    
    scanner.close();
    return;
  }
}


Measured memory_bytes: 42432
#include <bits/stdc++.h>
using namespace std;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define all(a) (a).begin(), (a).end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline int sz(T &x) { return x.size(); }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF  = 1<<30;


struct item {
  int v, w;
  // item (int v = 0, int w = 0) : v(v), w(w) {}
  bool operator<(const item &r) const { return w < r.w; }
  void operator+=(const item &r) { w += r.w, v += r.v; }
};


vector<item> enum_powerset(const vector<item> &is) {
  vector<item> a = {{0, 0}};
  for (auto &i : is) {
    auto b = a;
    for (auto &e : b) e += i;
    vector<item> c;
    merge(all(a), all(b), back_inserter(c));
    swap(a, c);
  }
  return a;
}


int solve(const vector<item> &is, int W) {
  int n = sz(is);
  auto a = enum_powerset({is.begin(), is.begin() + n/2});
  auto b = enum_powerset({is.begin() + n/2, is.end()});
  reverse(all(a));
 
  int ans = 0;
  int vbmax = -INF;
  auto itr = b.begin();
  for (auto &[va, wa] : a) {
    while (itr != b.end() && wa + itr->w <= W) {
      chmax(vbmax, itr->v);
      ++itr;
    }
    chmax(ans, va + vbmax);
  }
  return ans;
}


int main() {
  int n; cin >> n;
  vector<item> is(n);
  for (auto &[v, w] : is) cin >> v >> w;
  is.insert(is.begin(), {0, 0});

  int q; cin >> q;
  rep(_, q) {
    int v, l; cin >> v >> l;
    vector<item> qi;
    while (v) {
      qi.push_back(is[v]);
      v /= 2;
    }
    cout << solve(qi, l) << '\n';
  }
}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
#define B begin()
#define E end()
#define F first
#define S second
#define pub push_back
#define mkp make_pair
#define migmig ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long double ld;
typedef long long ll; 
typedef vector<ll> vll;
typedef map<ll,ll> mll;
const ll N=1e5+5;
ll n, m;
vector< pair<ll,ll> >g;
ll parent[N];
int root (int a){
    if(parent[a]==0)
        return a;
    parent[a]=root(parent[a]);
    return root(parent[a]);
}
void mrg(int a,int b){
    parent[root(a)]=root(b);
}
vll mst;
void find_mst(){
	sort (g.B,g.E);
	mst.clear();
	for(ll i=0; i<m; i++){
		int f=g[i].F;
		int t=g[i].S;
		if(root(f)!=root(t)){
		    mst.push_back(g[i].F);
			mrg(f,t);
		}
	}
}ll f, t;
int main(){
	cin>>n>>m;
	g.clear();
	for(int i=0; i<m; i++){
		cin>>f>>t;
		g.pub(mkp(f,t));
	}
    find_mst();	
    cout<<n-1-mst.size();
}











Measured memory_bytes: 7192
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)


int main(){
  int n;
  cin >> n;
  vl vec(1001, 0);
  rep(i, n){
    int num;
    cin >> num;
    vec[num]++;
  }
  vl sum(1001, 0);
  sum[0] = 0;
  rep(i, 1, 1001){
    sum[i] = sum[i-1] + vec[i];
  }
  int ans = 0;
  rep(i, 1, 999){
    rep(j, i+1, 1000){
      ans += vec[i]*vec[j]*(sum[min(i+j-1, (ll)1000)]-sum[j]);
    }
  }
  rep(i, 1, 1001){
    ans += vec[i]*(vec[i]-1)*(vec[i]-2)/6;
    ans += vec[i]*(vec[i]-1)*sum[i-1]/2;
    ans += vec[i]*(vec[i]-1)*(sum[min(i+i-1, (ll)1000)]-sum[i])/2;
  }
  cout << ans << endl;
  return 0;
}
      


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <string>
#include <functional>
#include <math.h>
#include <utility>
using namespace std;
int mer[350],a,b,c,N;
vector<int> memo;
int check(int i,int j,int k){
	int ans=-1;
	if(mer[i]!=1)ans=i;
	if(mer[j]!=1){
		if(ans!=-1)return -1;
		else ans=j;
	}
	if(mer[k]!=1){
		if(ans!=-1)return -1;
		else ans=k;
	}
	return ans;
}
void solve()
{
	while(cin>>a>>b>>c,a&&b&&c){
		cin>>N;
		fill(mer,mer+a+b+c,2);
		memo.clear();
		for(int s=0;s<N;s++){
			int i,j,k,r;cin>>i>>j>>k>>r;
			i--;j--;k--;
			if(r==1)mer[i]=mer[j]=mer[k]=1;
			else memo.push_back(i+(j-a)*100+(k-a-b)*10000);
		}
		for(vector<int>::iterator it=memo.begin();it!=memo.end();it++){
			int d=memo.at(it-memo.begin());
			int i=d%100;
			int j=((d-i)/100)%100+a;
			int k=(d-i-(j-a)*100)/10000+a+b;
			if(check(i,j,k)!=-1){
				mer[check(i,j,k)]=0;
			}
		}
		for(int i=0;i<a+b+c;i++)cout<<mer[i]<<endl;
	}
	return;
}
int main(){
	solve();
	return 0;
}

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

int main() {
#ifdef LOCAL_DEFINE
	//freopen("data.in", "rt", stdin);
	//freopen("data.out", "w", stdout);
	long long _begin_time = clock();
#endif
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n, k;
	cin >> n >> k;
	long long ans;
	if(k & 1) {
		long long x = n / k;
		ans = x * x * x;
	} else {
		long long x = n / k, y = n / (k >> 1) - x;
		ans = x * x * x + y * y * y;
	}
	cout << ans << '\n';

#ifdef LOCAL_DEFINE
	long long _end_time = clock();
	cerr << "time = " << _end_time - _begin_time << " ms\n";
#endif
	return 0;
}

Measured memory_bytes: 384
n,q = map(int,input().split())
s = input()
questions = [tuple(map(int,input().split())) for _ in range(q)]
A_Flag = False
t = [0]*(n + 1)
for i in range(0,n):
  if s[i:i+2] == "AC":
    t[i + 1] = t[i] + 1
  else:
    t[i + 1] = t[i]
for i in range(q):
  l,r = questions[i]
  print(t[r - 1] - t[l - 1])

Measured memory_bytes: 19792
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

int main(){
    ll n, m;
    cin >> n >> m;
    map<ll, vector<ll>> albeit;
    for(int i = 0; i < n; ++i){
        ll a, b;
        cin >> a >> b;
        albeit[a].push_back(b);
    }
    priority_queue<ll> q;
    ll ans = 0;
    for(int i = 1; i <= m; ++i){
        if(albeit.count(i)){
            for(ll x : albeit.at(i)){ q.push(x); }
        }
        if(!q.empty()){
            ans += q.top();
            q.pop();
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main(){


  int a,b,c,d,e;
  int p,j,sum;
  
  cin >> a>>b>>c>>d>>e;

  sum=a;
  if(b>c){
    if(sum>c) sum=c;
  }else if(sum>b) sum=b;

  if(d>e){
    sum+=e;
  }else sum+=d;

  sum -= 50;
  cout << sum <<endl;

  
  
  return 0;
}



Measured memory_bytes: 3080
from collections import Counter
n,k=map(int,input().split())
a=list(map(int,input().split()))

cnt=Counter(a)
cnt_len=len(cnt)
cnt=sorted(list(cnt.values()))
ans=0
if cnt_len<k:
    print(0)
    exit()
for i in range(cnt_len-k):
    ans+=cnt[i]
print(ans)

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

using namespace std;

int cnt[25];

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	memset(cnt,0,sizeof(cnt));

	int n,t;
	int res = 0;

	cin >> n;

	cnt[0] = 1;

	for(int i=0;i<n;i++)
	{
		cin >> t;
		if(t>12)
		{
			t = 24 - t;
		}
		if(cnt[t]<=1)
		{
			if(cnt[t]==1 && t==12)
			{
				cout << 0 << '\n';
				return 0;
			}
			cnt[t]++;
		}
		else
		{
			cout << 0 << '\n';
			return 0;
		}
	}

	for(int i=0;i<(1<<13);i++)
	{
		vector <int> v;
		//v.push_back(0);
		for(int j=0;j<13;j++)
		{
			int x = j;
			if(cnt[x]==2)
			{
				v.push_back(x);
				v.push_back(24-x);
			}
			else if(cnt[x]==1)
			{
				if(i&(1<<j))
				{
					v.push_back(24-x);
				}
				else
				{
					v.push_back(x);
				}
			}
		}
		sort(v.begin(),v.end());
		int Min = 24;
		for(int j=0;j<v.size();j++)
		{
			for(int k=j+1;k<v.size();k++)
			{
				int d = v[k] - v[j];
				d = min(24-d,d);
				Min = min(Min,d);
			}
		}
		res = max(res,Min);
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll n;cin>>n;
    vector<vector<double> >dp(n+1,vector<double>(n+1));
    dp[0][0]=1.00;
    rep(i,n){
        double p;cin>>p;
        rep(j,n){
            dp[i+1][j]+=dp[i][j]*(1.00-p);
            dp[i+1][j+1]+=dp[i][j]*p;
        }
    }
    double ans=0.000;
    rep(i,n+1){
        if(i>n-i)ans+=dp[n][i];
    }
    cout<<setprecision(15)<<ans<<endl;
}

Measured memory_bytes: 70656
int main(){
    int h,w,i,j;
    char a[128][128];
    scanf("%d%d",&h,&w);
    for(i = 0;i < h;i++){scanf("%s",a[i]);}
    for(i = 0;i < h+2;i++){
        for(j = 0;j < w+2;j++){
            if((i == 0 || i == h+1) || (j == 0 || j == w+1)){printf("%c",'#');}
            else{printf("%c",a[i-1][j-1]);}
        }
        printf("\n");
    }
    return 0;
}

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

#define __INIT_CC__ ios::sync_with_stdio(false); \
	cin.tie(0);

#ifdef __WIN32__
	char getchar_unlocked() {return getchar();}
#endif

#define FOR(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<(_t);++(_i))
#define FORN(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i<=(_t);++(_i))
#define FORD(_i,_n,_m) for(int (_i)=(_n),_t=(_m);_i>=(_t);--(_i))
#define RESET(_a,_value) memset(_a,_value,sizeof(_a))
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ff first
#define ss second
#define mp make_pair
#define SIZE(_a) (int)_a.size()
#define VSORT(_a) sort(_a.begin(),_a.end())
#define SSORT(_a,_val) sort(_a,_a+(_val))
#define ALL(_a) _a.begin(),_a.end()
#define mt make_tuple
#define _get(_tuple,_i) get<_i>(_tuple)
#define eb emplace_back
 
using namespace std;

using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<ii>;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll,ll>;
using vpll = vector<pll>;
using vll = vector<ll>;
using pdd = pair<double,double>;
using vpdd = vector<pdd>;
template <typename T> using uset = unordered_set<T>;
template <typename T> using umultiset = unordered_multiset<T>;
template <typename K, typename V> using umap = unordered_map<K, V>;
template <typename K, typename V> using umultimap = unordered_multimap<K, V>;

const int dr[] = { 1, 0,-1, 0, 1, 1,-1,-1};
const int dc[] = { 0, 1, 0,-1, 1,-1,-1, 1};
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const ll INFLL = 0x7FFFFFFFFFFFFFFFLL;
const double pi = acos(-1);

template <typename T> T take(queue<T> &O) {T tmp=O.front();O.pop();return tmp;}
template <typename T> T take(stack<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T> T take(priority_queue<T> &O) {T tmp=O.top();O.pop();return tmp;}
template <typename T>
inline bool inRange(const T& z, const T& a, const T& b){return a <= z && z <= b;}

void OPEN(const string& in = "input.txt", const string& out = "output.txt")
{
	freopen(in.c_str(), "r", stdin);
	freopen(out.c_str(), "w", stdout);
	return ;
}

//using sokokaleb's template v4.0

#define N 100005
int n, k;
int arr[N];

int main(int argc, char** argv) {
	__INIT_CC__
	cin >> n >> k;
	FOR (i, 0, n) cin >> arr[i];
	if (k > *max_element(arr, arr + n)) {
		cout << "IMPOSSIBLE\n";
		return 0;
	}
	int gcd = arr[0];
	FOR (i, 1, n) {
		gcd = __gcd(gcd, arr[i]);
	}
	FOR (i, 0, n) {
		if ((k - arr[i]) % gcd == 0 || k == arr[i]) {
			cout << "POSSIBLE\n";
			return 0;
		}
	}
	cout << "IMPOSSIBLE\n";
	return 0;
}


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

int main(){
    int a, b;
    cin >> a >> b;
    if(a%2 == b%2){
        if(a == b) cout << 0 << endl;
        else cout << (a+b)/2 << endl;
    }
    else cout << "IMPOSSIBLE" << endl;
}


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

int main()
{
int n,k,sum=0;

    cin>>n>>k;
    int d[k],b[n]={0};
    for(int i=0;i<k;i++){
        cin>>d[i];
        int a[k][d[i]];
        for(int j=0;j<d[i];j++){
            cin>>a[i][j];
            b[a[i][j]-1]=1;
        }
    }
     for(int i=0;i<n;i++){
        if(b[i]==0){
            sum++;
        }

     }
     cout<<sum;

}


Measured memory_bytes: 3672
#include<bits/stdc++.h>
#define in inline
#define int long long
#define re register
using namespace std;
in int read() {
	re int t=0;
	re char v=getchar();
	while(v<'0'||v>'9')v=getchar();
	while(v>='0'&&v<='9') {
		t=(t<<3)+(t<<1)+(v^48);
		v=getchar();
	}
	return t;
}
int n,m,ans[100002],A,B,C,dp[100002][3][3][3],pre[100002][3][3][3];
char s[12];
long long sum;
inline void work(re int x,re int a,re int b,re int c){
	if(x==0)return;
	re int xx=pre[x][a][b][c];
	if(xx==1)++a,--b;
	if(xx==2)--a,++b;
	if(xx==3)++a,--c;
	if(xx==4)--a,++c;
	if(xx==5)++b,--c;
	if(xx==6)--b,++c;
	work(x-1,a,b,c);
	if(xx==2||xx==4)puts("A");
	if(xx==1||xx==6)puts("B");
	if(xx==3||xx==5)puts("C");
}
signed main(){
	n=read();A=read();B=read();C=read();
//	if(A+B+C==2ll)return 1;
	if(A+B+C!=2ll){
		for(re int i=1;i<=n;++i){
			scanf("%s",s+1);
			if(s[1]=='A'&&s[2]=='B'){
				if(A>B){--A;++B;ans[i]=2;
				}
				else{
					if(B==0){
						puts("No");
						return 0;
					}
					--B;++A;
					ans[i]=1;
				}
			}
			if(s[1]=='A'&&s[2]=='C'){
				if(A>C){
					--A;++C;
					ans[i]=3;
				}
				else{
					if(C==0){
						puts("No");
						return 0;
					}
					--C;++A;
					ans[i]=1;
				}
			}
			if(s[1]=='B'&&s[2]=='C'){
				if(B>C){
					--B;++C;
					ans[i]=3;
				}
				else{
					if(C==0){
						puts("No");
						return 0;
					}
					--C;++B;
					ans[i]=2;
				}
			}
		}
		puts("Yes");
		for(re int i=1;i<=n;++i){
			if(ans[i]==1)puts("A");
			if(ans[i]==2)puts("B");
			if(ans[i]==3)puts("C");
		}
	}
	else{
		dp[0][A][B][C]=1;
		for(re int ii=1;ii<=n;++ii){
			scanf("%s",s+1);
			if(s[1]=='A'&&s[2]=='B'){
				for(re int i=0;i<=1;++i){
					for(re int j=1;j<=2;++j){
						for(re int k=0;k<=2;++k){
							if(dp[ii-1][i+1][j-1][k]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=1;
							}
						}
					}
				}
				for(re int i=1;i<=2;++i){
					for(re int j=0;j<=1;++j){
						for(re int k=0;k<=2;++k){
							if(dp[ii-1][i-1][j+1][k]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=2;
							}
						}
					}
				}
			}
			if(s[1]=='A'&&s[2]=='C'){
				for(re int i=0;i<=1;++i){
					for(re int j=0;j<=2;++j){
						for(re int k=1;k<=2;++k){
							if(dp[ii-1][i+1][j][k-1]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=3;
							}
						}
					}
				}
				for(re int i=1;i<=2;++i){
					for(re int j=0;j<=2;++j){
						for(re int k=0;k<=1;++k){
							if(dp[ii-1][i-1][j][k+1]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=4;
							}
						}
					}
				}
			}
			if(s[1]=='B'&&s[2]=='C'){
				for(re int i=0;i<=2;++i){
					for(re int j=0;j<=1;++j){
						for(re int k=1;k<=2;++k){
							if(dp[ii-1][i][j+1][k-1]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=5;
							}
						}
					}}
				for(re int i=0;i<=2;++i){
					for(re int j=1;j<=2;++j){
						for(re int k=0;k<=1;++k){
							if(dp[ii-1][i][j-1][k+1]){
								dp[ii][i][j][k]=1;
								pre[ii][i][j][k]=6;
							}
						}
					}
				}
		}
		}
		for(re int i=0;i<=2;++i){
			for(re int j=0;j<=2;++j){
				for(re int k=0;k<=2;++k){
					if(dp[n][i][j][k]){
						puts("Yes");
						work(n,i,j,k);
						return 0;
					}
				}
			}
		}
		puts("No");
	}
}

Measured memory_bytes: 49004
import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)


Measured memory_bytes: 159476
/*
 * Matheus Oliveira
 * 09:56:20 02/05/2020
 * d.cpp
*/

#include <bits/stdc++.h>
using namespace std;

#define EPS
#define INF
#define MAXN
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define sc(x) scanf("%d", &x);
#define sc2(x, y) scanf("%d %d", &x, &y);
#define sc3(x, y, z) scanf("%d %d %d", &x, &y, &z);
#define debug(x) printf("%s: %d\n", #x, x);
#define debugarr(x, bg, ed) printf("%s: ", #x); for(int i = bg; i < ed; i++) printf("%d%c", x[i], (i == ed-1) ? '\n' : ' ');

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

int main() {
	double val;
	ll a, b, n, x, ans = 0;
	scanf("%lld %lld %lld", &a, &b, &n);
	
	//ll testMaxi = 0;
	//for(ll x = 0; x <= n; x++) {
	//	val = floor(a*x/((double) b)) - a * floor(x/((double) b));	
	//	//printf("f(%f) - %lld * f(%f) = %f. x=%lld\n", a*x/((double) b), a, x/((double) b), val, x);
	//	testMaxi = max(testMaxi, (ll) val);
	//}

	x = n;
	val = floor(a*x/((double) b)) - a * floor(x/((double) b));
	ans = val;

	x = b - 1;
	if(x > 0 and x <= n) val = floor(a*x/((double) b)) - a * floor(x/((double) b));
	ans = max(ans, (ll)val);

	//printf("a: %lld, b: %lld, n: %lld\n", a, b, n);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3872
n, c = map(int, input().split())
XV = [tuple(map(int, input().split())) for i in range(n)]
X = [x for x, v in XV]
V = [v for x, v in XV]
S = [0]
for i in range(n):
    S.append(S[-1]+V[i])
# 右回りから行く場合
A = [0]
for i in range(1, n+1):
    A.append(max(A[-1], S[i]-2*X[i-1]))
B = []
for i in range(n):
    B.append(S[n]-S[i]-(c-X[i]))
B.append(0)
ans0 = max([A[i]+B[i] for i in range(n+1)])
# 左回りから行く場合
A = [0]
for i in range(1, n+1):
    A.append(max(A[-1], S[i]-X[i-1]))
B = []
for i in range(n):
    B.append(S[n]-S[i]-2*(c-X[i]))
B.append(0)
ans1 = max([A[i]+B[i] for i in range(n+1)])
print(max(ans0, ans1))


Measured memory_bytes: 35128
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.List
import Data.Maybe
import Data.Ord
import qualified Data.Vector as VC
import qualified Data.Vector.Mutable as VM

readNums :: IO [Integer]
readNums = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readNumLists :: Int -> IO [[Integer]]
readNumLists n = replicateM n (map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine)

readStrings :: IO [String]
readStrings = map BS.unpack . BS.words <$> BS.getLine

readStringLists :: Int -> IO [[String]]
readStringLists n = replicateM n (map BS.unpack . BS.words <$> BS.getLine)

toTuple :: [a] -> (a, a)
toTuple (x:y:_) = (x, y)

p s = putStr (show s ++ " ")

main :: IO ()
main = do
  (n:_) <- readNums
  p <- readNums
  print $ solve p

solve p = f (head p) 0 p
  where
    f acc m [] = m
    f acc m (x:xs)
      | acc >= x = f x (m + 1) xs
      | otherwise = f acc m xs

Measured memory_bytes: 4348