akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <boost/multiprecision/cpp_int.hpp>
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <set>
#include <numeric>
#include <sstream>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
#include<iomanip>
namespace mp = boost::multiprecision;
using namespace std;
using ull = unsigned long long;
using ld = long double;
using lll = boost::multiprecision::cpp_int;
using ll = long long;
#define FOR(i, N) for(ll i = 0; i < N; ++i)

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
// using int = ll;
ll gcd(ll m, ll n) {
    if(n == 0)
        return abs(m);
    return (gcd(n, m % n));
}
void putYN(bool b) {
    if(b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
ll combi(ll n, ll k) {
    ll r = 1, rr = 1;
    for(ll i = 0; i < k; ++i) {
        r *= (n - i);
        rr *= (i + 1);
        // r %= 1000000007;
        // rr %= 1000000007;
    }
    r /= rr;
    // r %= 1000000007;
    return r;
}
int main(){
  ll N,M;
  cin>>N>>M;
  map<ll,pair<bool,ll>> m;//pn, 正答したか,ペナルティ
  FOR(i,M){
    ll p;
    string s;
    cin>>p>>s;
    
    if(s=="AC"){
      if(m.find(p)==m.end()){
        m[p] = pair<bool,ll>(true,0);
      }else{
        m[p].first = true;
      }
    }else{
      if(m.find(p)==m.end()){
        m[p] = pair<bool,ll>(false,1);
      }else{
        if(m[p].first == false){
          m[p].second++;
        }
      }
    }
  }
  ll ans1=0,ans2=0;
  for(auto a:m){
    if(a.second.first==true){
      ans1++;
      ans2+=a.second.second;
    }
  }
  cout<<ans1<<" "<<ans2;
  return 0;
}


Measured memory_bytes: 6528
#include<stdio.h>
#include<stdlib.h>

/*
struct node{

  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node *Node;
Node root, NIL;

void insert(int k){

  int N;
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));

  z -> key = k;
  z -> left = NIL;
  z -> right = NIL;

  while(x != NIL){

    y=x;

    if(z -> key < x -> key)
      x = x->left;
    else
      x = x -> right;
    
  }

  z -> parent = y;

  if(y == NIL) root = z;

  else {
    if( z->key < y->key)
      y -> left = z;

    else {
      y -> right = z;
    }
    
    }
}

void inorder (Node u){

  if(u==NIL) return;

  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);

}



void preorder(Node u){
  
  if(u==NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
  
  }*/

int n,array[2000000];

void maxHeapify(int i)
{
  int l, r, largest, tmp;
  l = 2*i;//left
  r = 2*i+1;//right
  if ( l <= n && array[l] > array[i] ) largest = l;
  else largest = i;
  if ( r <= n && array[r] > array[largest] ) largest = r;
  if ( largest != i ){
    tmp = array[i];
    array[i] = array[largest];
    array[largest] = tmp;
    maxHeapify(largest);
  }

}






int main(){
  int i,key;
  //int array[100000];

  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&array[i]);
    
  }

  for(i=n/2; i>=1 ;i--){
    /* printf("node %d: key = %d, ",i,array[i]);
       if(i/2 >= 1) printf("parent key = %d, ",array[i/2]);
       if(i*2 <= n) printf("left key = %d, ",array[i*2]);
       if(i*2+1 <= n) printf("right key = %d, ",array[i*2+1]);
       printf("\n");*/

    maxHeapify(i);
  }

 
  for(i=1;i<=n;i++) printf(" %d",array[i]);
  printf("\n");
  
  return 0;
}



Measured memory_bytes: 3680
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
template<class T> inline bool chmin(T& a, T b){if(a>b){a=b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a=b;return true;}return false;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw3(15,1);vector<ll> pw10(19,1);

ll C,D;
ll f(ll x){
    return x-(x/C)-(x/D)+(x/lcm(C,D));
}

int main(){
    {rep1(i,14) pw3[i]=3*pw3[i-1];}
    {rep1(i,18) pw10[i]=10*pw10[i-1];}
    
    ll A,B; cin>>A>>B>>C>>D;
    cout<<f(B)-f(A-1)<<endl;
}


Measured memory_bytes: 3596
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define mem(x,v) memset(x,v,sizeof(x))
#define fi first
#define se second
#define lowbit(x) ((x)&-(x))
#define debug(x) cout << #x " = " << x << endl;
namespace IO{
	const int L = 1 << 15;
	char ibuf[L|1],*iS=ibuf,*iT=ibuf;
	char obuf[L|1],*oS=obuf,*oT=obuf+L;
	char c,st[66];int tp=0,f;
	inline char gc(){
		if(iS==iT) iT=(iS=ibuf)+fread(ibuf,sizeof(char),L,stdin);
		return (*iS++);
	}
	inline void flush() {
		fwrite(obuf,sizeof(char),oS-obuf,stdout);
		oS = obuf;
	}
	inline void pc(char c){*oS++=c;if(oS==oT) flush();}
	#define gc getchar
	#define pc putchar
	inline ll read(){
		ll x=0;f=1,c=gc();
		for(;!isdigit(c);c=gc())if(c=='-')f=-1;
		for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c&15);
		return x*f;
	}
	void write(ll x){
		if(!x) pc('0');if(x<0) pc('-'),x=-x;
		while(x) st[++tp]=x%10+'0',x/=10;
		while(tp) pc(st[tp--]);
	}
	void wri(ll x){write(x);pc(' ');}
	void writeln(ll x){write(x);pc('\n');}
	struct IOflusher{~IOflusher(){flush();}}_ioflusher_;
}
using IO::read;
using IO::writeln;
using IO::wri;
inline void gg(string s){cout << s << endl;exit(0);}
inline void gg(ll x){writeln(x);exit(0);}
const int maxn = 2e5+233;
int n,a[maxn],ans=0,v[2],p[2],nxt[3];
int main(){
	n = read();
	Rep(i,1,n) a[i] = read();
	Rep(i,1,n+1){
		p[0] = 0,p[1] = a[i] - a[i-1];
		if(p[0] < p[1]) swap(p[0],p[1]);
		nxt[0] = nxt[1] = 1e9,nxt[2] = 0;
		rep(j,0,2)rep(k,0,2)
			nxt[j+k] = min(nxt[j+k],max(0,v[j]+p[k]));
		int d=nxt[0]>a[i];ans+=d;
		rep(j,0,2) v[j] = nxt[j+d];
	}writeln(ans);
}

Measured memory_bytes: 4420
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'
#define INF 999999999
typedef long long int Int;
using ll = long long;
using VI = vector<int>;

int main(){
  int n;cin >> n;
  vector<int> d(n);
  int a=0,b=0;
  for(auto &i:d) cin >> i;
  sort(d.begin(),d.end());
  while(d.size()>1){
    a+=d.back();
    d.pop_back();
    b+=d.back();
    d.pop_back();
  }
  a+=d.back();
  //cout << a << endl << b << endl;
  cout << a-b << endl;
}


Measured memory_bytes: 256
package main

import (
  "fmt"
)

var h, n int 
const INF = 1000000000

func main() {
  fmt.Scanf("%d%d", &h, &n);

  dp := [10001]int{}
  for i := 1; i < h+1; i++ {
    dp[i] = INF
  }
  
  for i := 0; i < n; i++ {
    var a, b int;
    fmt.Scanf("%d%d", &a, &b);
    for j := 0; j < h; j++ {
      if j+a <= h {
        if dp[j+a] > dp[j]+b {
          dp[j+a] = dp[j]+b;
        }
      } else if dp[h] > dp[j]+b {
        dp[h] = dp[j]+b;
      }
    }
  }
  
  fmt.Println(dp[h])
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int h,w;
vector<string> s;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

class UnionFind{
private:
    vector<int> par,height,size;
public:
    UnionFind(int n){
        par.resize(n);
        REP(i,n){
            par[i] = i;
        }
        height.resize(n,0);
        size.resize(n,1);
    }
    int root(int x){
        if(par[x]==x){
            return x;
        }else{
            par[x] = root(par[x]);
            return par[x];
        }
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x==y)return;
        if(height[x]<height[y]){
            par[x]=y;
            size[y]+=size[x];
        }else{
            par[y]=x;
            size[x]+=size[y];
            if(height[x]==height[y])height[x]++;
        }
    }
    int cnt(int x){
        x=root(x);
        return size[x];
    }
};

int main(){
    cin >> h >> w;
    s.resize(h);
    REP(i,h){
        cin >> s[i];
    }
    UnionFind uf(h*w);
    Rep(y,h){
        Rep(x,w){
            REP(k,4){
                int ny = y+dy[k];
                int nx = x+dx[k];
                if(0<=ny&&ny<h&&0<=nx&&nx<w&&s[ny][nx]!=s[y][x]){
                    int t1 = y*w+x;
                    int t2 = ny*w+nx;
                    uf.unite(t1,t2);
                }
            }
        }
    }
    
    vector<int> cnt(h*w,0);
    vector<int> cnt2(h*w,0);
    
    Rep(y,h){
        Rep(x,w){
            int t = y*w+x;
            if(s[y][x]=='#'){
                cnt[uf.root(t)]++;
            }else{
                cnt2[uf.root(t)]++;
            }
        }
    }
    ll res = 0;
    REP(i,h*w){
        res += (ll)cnt[i]*cnt2[i];
    }
    put(res);
    return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
vector<int >valor;
vector<int>altura;
int n;
int main(){
    cin>>n;
    altura.resize(n);
    valor.assign(n,INT_MAX/2);
    for(int i=0;i<n;i++)cin>>altura[i];
    valor[n-1]=0;
    for(int i=n-2;i>=0;i--){
        if(i+2<=n-1)valor[i]=min(valor[i],abs(altura[i]-altura[i+2])+valor[i+2]);
        valor[i]=min(valor[i],abs(altura[i]-altura[i+1])+valor[i+1]);
        //cout<<i+1<<" "<<valor[i]<<"\n";
    }
    cout<<valor[0];
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#else
#define show(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N,M;
	cin >> N >> M;
	if(M%2){
		cout << -1 << endl;
		return 0;
	}
	VV<int> G(N);
	rep(i,M){
		int x,y;
		cin >> x >> y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	using P = pair<int,int>;
	V<P> ans;
	V<int> cnt(N);
	V<bool> vis(N);
	set<P> done;
	function<void(int,int)> dfs = [&](int v,int p){
		vis[v] = true;
		for(int u: G[v]) if(u != p){
			if(!vis[u]){
				dfs(u,v);
			}else if(done.count(P(u,v))){
				
			}else{
				ans.pb(P(u,v));
				cnt[u]++;
				done.insert(P(u,v));
				done.insert(P(v,u));
			}
		}
		if(p != -1){
			if(cnt[v]%2 == 0){
				ans.pb(P(p,v));
				cnt[p]++;
			}else{
				ans.pb(P(v,p));
				cnt[v]++;
			}
		}
	};
	dfs(0,-1);
	rep(i,N){
		assert(cnt[i]%2==0);
	}
	assert(ans.size() == M);
	rep(i,M) cout << ans[i].fs+1 << " " << ans[i].sc+1 << endl;
}


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

using namespace std;

using ll = long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n,k;
    cin>>n>>k;
    vector<int> v(n);
    for(auto &a : v) cin>>a;
    vector<double> p(n+1);
    for(int i=0;i<n;++i){
        int sum = 0;
        for(int j=1;j<=v[i];++j)sum+=j;
        p[i] = 1.0*sum/v[i];
    }
    vector<double > c(n+1,0);
    for(int i=0;i<n;++i)c[i+1] += c[i] + p[i];
    double ret = 0.0;
    for(int i=0;i<n;++i){
        if(i+k >= n+1)break;
        ret = max(c[i+k] - c[i],ret);
    }
    cout << fixed;
    cout << setprecision(15);
    cout << ret << endl;
    return 0;
}


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

int n;
std::string s[55], x;
int t[55], ans;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; ++i) {
		std::cin >> s[i] >> t[i];
	}
	std::cin >> x;
	int k = 1;
	while (s[k] != x) {
		++k;
	}
	for (int i = k + 1; i <= n; ++i) {
		ans += t[i];
	}
	std::cout << ans << std::endl;
}

Measured memory_bytes: 3632
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author P.Alizadeh
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int   ll;
typedef long double     ld;
typedef pair<ll,ll>     pll;
typedef complex<ld>     cld;

#define all(x)          x.begin(),x.end()
#define Sort(x)         sort(all(x))
#define kill(x)         return cout << x << endl, 0;
#define Mp              make_pair
#define X               first
#define Y               second
#define sep             " "
#define endl            "\n"
#define fastio          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define ld_io           cout << setprecision(10) << fixed;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll pw(ll a, ll b, ll md) {
    if (!b)
        return 1;
    if (b & 1)
        return a * pw(a * a % md, b / 2, md) % md;
    return pw(a * a % md, b / 2, md) % md;
}

const ll MAXN = 1e5 + 10,
         INF  = 8e18,
         MOD  = 1e9 + 7,
         LOG  = 32;
//const ld PI   = M_PI;

ll n, k, dp[110][MAXN], a[110];

int main()
{
    fastio;
    //ld_io;

    cin >> n >> k;
    for (ll i = 1; i <= n; i++)
        cin >> a[i];

    dp[0][0] = 1;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < MAXN; j++) {
            if (j == 0)
                dp[i][j] = 1;
            else if (j <= a[i])
                dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % MOD;
            else
                dp[i][j] = (dp[i][j-1] - dp[i-1][j-a[i]-1] + dp[i-1][j]) % MOD;
        }
    }

    if (dp[n][k] >= 0)
        cout << dp[n][k] % MOD << endl;
    else
        cout << (dp[n][k] % MOD) + MOD << endl;

    return 0;
}



Measured memory_bytes: 79360
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;

long long N, X[1009], Y[1009], H[1009]; vector<tuple<long long, long long, long long>>vec;

int main() {
	cin >> N; tuple<long long, long long, long long>G = make_tuple(-1, -1, -1);
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i] >> H[i];
		if (H[i] >= 1) G = make_tuple(X[i], Y[i], H[i]);
	}
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			long long V = get<2>(G) + abs(get<0>(G) - i) + abs(get<1>(G) - j); V = max(V, 0LL); bool flag = true;
			for (int k = 1; k <= N; k++) {
				long long VV = V - abs(X[k] - i) - abs(Y[k] - j); VV = max(VV, 0LL);
				if (H[k] != VV) flag = false;
			}
			if (flag == true) cout << i << " " << j << " " << V << endl;
		}
	}
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

int main(){
    int n;
    scanf("%d", &n);
    int k = 1;
    while(k*(k+1)/2 < n) ++k;
    vector<int> v;
    rep(i, 30)if(((k*(k+1)/2-n) >> i) & 1) v.push_back(1<<i);
    int cur = 0;
    For(i, 1, k+1){
        if(cur < v.size() && i == v[cur]){
            ++cur;
            continue;
        }
        printf("%d\n", i);
    }
}

Measured memory_bytes: 256
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n = int(input())
c = list(input())
r = 0
w = 0
for i in range(n):
    if c[i] == "R":
        r += 1
    else:
        w += 1
ans = 0
for i in range(r):
    if c[i] != "R":
        ans += 1
print(ans)





Measured memory_bytes: 73384
#include <bits/stdc++.h>
#define rep(i,n) for ( int i = 0; i < (n); ++i )
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long int;
const long long int INF = 1001001001001001LL;
const int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);

    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    vector<int> c(n-k+1, 0);

    rep(i,k) {
        cin >> p[i];
        c[0] += p[i];
    }

    rep(i, n-k) {
        cin >> p[k+i];
        c[i+1] = c[i] - p[i] + p[k+i];
    }

    cout << (double) *max_element( all(c) ) / 2.0 + 0.5 * (double) k << endl;
    return 0;
}

Measured memory_bytes: 1792
void main() {
	auto N = ri;
	auto H = readAs!(int[]);
	int tmp = 0;
	ulong cnt;
	foreach(v; H) {
		if(v >= tmp) {
			tmp = v;
			cnt++;
		}
	}
	cnt.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


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

#define sz(x) (int)x.size()
#define ld long double
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

const ll INF = 2e18;
const ll MOD = 1e9 + 7;

ll n, a, b, res = 0;
vector<ll> p2, g;
vector<vector<ll>> dp1, dp2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b;
    p2.assign(n + 1, 1);
    for(int i = 0; i < n; ++i){
        p2[i + 1] = p2[i] * 2;
        p2[i + 1] %= MOD;
    }
    if(a > b) swap(a, b);
    if(b == 1){
        cout << p2[n];
        return 0;
    }
    dp1.assign(n + 1, vector<ll>(2, 0));
    dp2.assign(n + 1, vector<ll>(2, 0));
    dp1[0][0] = dp1[0][1] = 1;
    for(int i = 1; i <= n; ++i){
        for(int k = 0; k < 2; ++k){
            for(int j = 1; j <= i; ++j){
                if(!k && j < a) continue;
                dp1[i][k] += dp1[i - j][k ^ 1];
                dp1[i][k] %= MOD;
            }
        }
    }
    g.assign(n + 1, 0);
    g[0] = 1;
    for(int i = 1; i <= n; ++i){
        g[i] = dp1[i][0] + dp1[i][1];
        g[i] %= MOD;
    }
    for(ll i = 1; i < n; ++i){
        if(i < a) dp2[i][0]++;
        for(ll j = 0; j < min(i, a); ++j){
            dp2[i][0] += dp2[i - j][1];
            dp2[i][0] %= MOD;
        }
        if(i < b){
            dp2[i][1] += g[i - 1];
            dp2[i][1] %= MOD;
        }
        for(ll j = 1; j < min(i, b); ++j){
            ll w = j == 1 ? 1 : g[j - 2];
            dp2[i][1] += dp2[i - j][0] * w;
            dp2[i][1] %= MOD;
        }
        if(n - i < b){
            res += dp2[i][0] * g[n - i - 1];
            res %= MOD;
        }
        if(n - i < a){
            res += dp2[i][1];
            res %= MOD;
        }
    }
    cout << ((p2[n] - res)%MOD + MOD)%MOD;
    return 0;
}

Measured memory_bytes: 4212
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
#define fst first
#define snd second
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
const ll maxn=1e5+4;
ll f[2][3];
const ll EQ=0,LS=1,GR=2;
void solve(long long N, vector<long long> A){
	ll cur=0,nxt=1;
	for (ll state=0;state<3;state++) f[cur][state]=1;
	for (ll x=1;x<N;x++) {
		for (ll state=0;state<3;state++) {
			f[nxt][state]=INF;
		}
		for (ll s=0;s<3;s++) {
			ll a=A[x-1],b=A[x];
			if (s==EQ&&!(a==b)) continue;
			if (s==LS&&!(a<=b)) continue;
			if (s==GR&&!(a>=b)) continue;
			chkmin(f[nxt][s],f[cur][s]);
			chkmin(f[nxt][s],f[cur][EQ]);
		}
		for (ll t=0;t<3;t++) chkmin(f[nxt][EQ],f[cur][t]+1);
		swap(cur,nxt);
	}
	ll ans=INF;
	for (ll s=0;s<3;s++) chkmin(ans,f[cur][s]);
	printf("%lld\n",ans);
}

int main(){	
	ios_base::sync_with_stdio(false); cin.tie(0);
	long long N;
	scanf("%lld",&N);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
	}
	solve(N, A);
	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

vector<pair<char, ll>> RunLengthCompression(const string& s) {
  ll cur = 1;
  ll n = SZ(s);
  vector<pair<char, ll>> run;
  REP(i, n - 1) {
    if (s[i] == s[i + 1]) {
      cur++;
      continue;
    }
    run.push_back(make_pair(s[i], cur));
    cur = 1;
  }
  run.push_back(make_pair(s[n - 1], cur));
  return run;
}

int main() {
  ll n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  auto run = RunLengthCompression(s);
  vector<ll> one = {0}, zero = {0};
  if (run[0].first == '0') {
    one.push_back(0);
  }
  FOREACH(x, run) {
    if (x.first == '1') {
      one.push_back(x.second + one[SZ(one) - 1]);
    } else {
      zero.push_back(x.second + zero[SZ(zero) - 1]);
    }
  }
  if (run[SZ(run) - 1].first == '0') {
    one.push_back(one[SZ(one) - 1]);
  }

  // 111...1
  if (SZ(one) == 2) {
    cout << one[1] << endl;
    return 0;
  }
  // 1010...01
  ll ans = 0;
  ll x = SZ(zero);
  FOR(i, 1, x) {
    ll len_zero = zero[min(i + k - 1, x - 1)] - zero[i - 1];
    ll len_one = one[min(i + k, x)] - one[i - 1];
    ans = max(ans, len_one + len_zero);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3312
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
#define fi first
#define se second
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

string s[10]={"1111110",
			  "0110000",
			  "1101101",
			  "1111001",
			  "0110011",
			  "1011011",
			  "1011111",
			  "1110010",
			  "1111111",
			  "1111011"};

signed main() {
	int n;
	while(1){
		cin >> n;
		if(n == -1) break;
		int a;
		string now = "0000000";
		rep(i, 0, n){
			cin >> a;
			string ans = "";
			repb(j, 6, 0){
				if(now[j] != s[a][j]) cout<< 1;
				else cout<< 0;
			}
			cout << endl;
			now = s[a];
		}
	}
}

Measured memory_bytes: 1208
n,m,q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

def calc(l):
    res = 0
    for a,b,c,d in abcd:
        if l[b-1]-l[a-1]==c:
            res += d
    # print(l,res)
    return res

def f(l):
    if len(l)==n:
        return calc(l)
    
    res = 0
    for x in range(l[-1],m+1):
        res = max(res, f(l+[x]))
    return res

res = 0
for x in range(1,m+1):
    res = max(res, f([x]))
print(res)

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

int main(){
    int N, M;
    std::cin >> N >> M;
    std::vector< int > A(N);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }
    std::vector< std::pair< int, int > > CB(M);
    for(int i=0; i<M; i++){
        std::cin >> CB[i].second >> CB[i].first;
    }
    
    std::sort(A.begin(), A.end());
    std::sort(CB.begin(), CB.end());
    
    int A_index = A.size() - 1;
    int CB_index = CB.size() - 1;
    int cur_CB_cnt = 0;
    long long ans = 0;
    for(int i=0; i<N; i++){
        if(CB_index < 0 || A[A_index] > CB[CB_index].first){
            ans += A[A_index];
            A_index--;
        }else{
            ans += CB[CB_index].first;
            cur_CB_cnt++;
            if(cur_CB_cnt == CB[CB_index].second){
                CB_index--;
                cur_CB_cnt = 0;
            }
        }
    }
    
    std::cout << ans << std::endl;
    
    return 0;
}



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

int main() {
	int x;
	cin >> x;
	int count = 0;
	int i = 0;
	int p = 0;
	while(p<x){
		p+=i;
		i+=1;
		count += 1;
	}
	cout << count -1 << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ar array

const ll mod = 1e9 + 7;

ll pwr(ll a, ll b) {
    ll ret = 1;
    while (b > 0) {
        if (b % 2 == 1) ret = ret * a % mod;
        a = a * a % mod;
        b /= 2; 
    }
    return ret;
}

const int N = 2e6 + 5;
ll f[N], inv[N];

ll C(int n, int k) {
    if (k > n || k < 0) return 0;
    return f[n] * (inv[k] * inv[n - k] % mod) % mod;
}

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

    int k, n;
    string s;
    cin >> k >> s;
    n = (int) s.size() + k;
    
    f[0] = 1; inv[0] = 1;
    for (int i = 1; i < N; i++) {
        f[i] = (ll) f[i - 1] * i % mod;
        inv[i] = pwr(f[i], mod - 2);
    }

    ll ans = 0;
    for (int i = 0; i < (int) s.size(); i++) {
        ans = (ans + pwr(25, n - i) * C(n, i) % mod) % mod;
    }
    ans = (pwr(26, n) - ans + mod) % mod;
    
    cout << ans << '\n';
}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;
const int INF = 2147483647;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
	bool ret = true;
	if (x < 2) {
		ret = false;
	}
	for (LL i = 2; i <= sqrt(x); i++) {
		if (x%i == 0) {
			ret = false;
		}
	}
	return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a,b) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define int long long
using namespace std;

int dp[2][3000][3000];
int v[3000];

int r(int s, int e, int t)
{
    if (s==e)
    {dp[t][s][e] = v[s];if(t%2)return -v[s];else return v[s];}
    if (dp[t][s][e])return dp[t][s][e];
    
    if (t%2==0)
        dp[t][s][e] = max(r(s+1, e, 1-t)+v[s], r(s, e-1, 1-t)+v[e]);
    else
        dp[t][s][e] = min(r(s+1, e, 1-t)-v[s], r(s, e-1, 1-t)-v[e]);
   // cout <<t << " " << s << " " << e << endl;
    return dp[t][s][e];
}

signed main()
{
   int n;cin>>n;for(int i=0;i<n;++i)cin>>v[i];
   cout << r(0, n-1, 0) << endl;
  /* cout << endl;
   for (int k=0;k<2;++k){
   for (int i=0;i<n;++i)
   {
       for (int j=0;j<n;++j)cout<<dp[k][i][j]<<" ";
       cout << endl;
   }cout<<"-------\n\n";}*/
   return 0;
}

Measured memory_bytes: 140032
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cstring>
#include <functional>
#include <iostream>
#include <istream>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <array>
#include <complex>
#include <limits>

using namespace std;
#define ll long long
#define reg register int
const int N = 100000;


class Solve{
	public:
		void solution(){
			int n, x, t;
            cin >> n >> x >> t;
            int tcopy = t;
            int xcopy = x;
            while(x<n){
                t = t + tcopy;
                x = x + xcopy;
            }
			cout << t << endl;
			return;
		}

};

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	Solve s;
	// int testCase;
	// scanf("%d", &testCase);
	// while(testCase--)
		s.solution();
	return 0;
}

Measured memory_bytes: 3644
import copy

n = int(input())
a = list(map(int, input().split(' ')))
sum_list = [0] * n
past = 0
for i in range(n):
    if i > 0:
        sum_list[i] = sum_list[i-1] + a[i]
    else:
        sum_list[0] = a[i]
sum1 = copy.copy(sum_list)
sum2 = copy.copy(sum_list)

ans = 0
count = 0
for i in range(n):
    # a[0]がプラス
    num = 0
    sum1[i] += past
    if i % 2 == 0 and sum1[i] <= 0:
        num = (abs(sum1[i]) + 1)
        sum1[i] += num
        past += num
    if i % 2 == 1 and sum1[i] >= 0:
        num = (abs(sum1[i]) + 1)
        sum1[i] -= num
        past -= num
    count += num

ans = count
count = 0
past = 0

for i in range(n):
    # a[0]がマイナス
    num = 0
    sum2[i] += past
    if i % 2 == 0 and sum2[i] >= 0:
        num = (abs(sum2[i]) + 1)
        sum2[i] -= num
        past -= num
    if i % 2 == 1 and sum2[i] <= 0:
        num = (abs(sum2[i]) + 1)
        sum2[i] += num
        past += num
    count += num

ans = min(ans, count)
print(ans)

Measured memory_bytes: 16680
import java.util.Scanner;

public class Main{

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        // input
        final int NUM = scan.nextInt();
        int[] town = new int[NUM+1];
        int[] hero = new int[NUM];
        for(int i = 0; i < NUM + 1; i++){
            town[i] = scan.nextInt();
        }
        for(int i = 0; i < NUM; i++){
            hero[i] = scan.nextInt();
        }

        // search
        long sum = 0;
        int temp = Math.min(town[0], hero[0]);
        town[0] -= temp;
        hero[0] -= temp;
        sum += temp;
        for(int i = 1; i < NUM; i++){
            temp = Math.min(town[i], hero[i - 1]);
            town[i] -= temp;
            hero[i - 1] -= temp;
            sum += temp;
            temp = Math.min(town[i], hero[i]);
            town[i] -= temp;
            hero[i] -= temp;
            sum += temp;
        }
        temp = Math.min(town[NUM], hero[NUM - 1]);
        town[NUM] -= temp;
        hero[NUM - 1] -= temp;
        sum += temp;

        // answer
        System.out.println(sum);


        
    }
}

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

int main()
{
    
    string S;
    cin >> S;
        

    if(S[0]=='A'){
      if(!islower(S[1]))
      {
          cout << "WA" << endl;
          return 0;
      }

      int count = 0;
      for(int i=2; i<S.size()-1; i++)
      {  
        if(S[i]=='C') count++;
        else if(!islower(S[i])) 
        { 
          cout << "WA" << endl;
          return 0;
        }
      }
      if(count==1&&islower(S[S.size()-1])) cout << "AC" << endl;
      else cout << "WA" << endl;
    }
    
    else {
      cout << "WA" << endl;
    }
	return 0;
}


Measured memory_bytes: 256
// ABC061
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

#define INF 10000000000
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> s(H);

    for(int i = 0; i < H; i++) cin >> s[i];

    for(int j = 0; j < W+2; j++) cout << '#';
    cout << endl;

    for(int i = 0; i < H; i++)
    {
        cout << '#';
        cout << s[i];
        cout << '#' << endl;
    }

    for(int j = 0; j < W+2; j++) cout << '#';
    cout << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);

int main(){
  int A, B, H, M;
  cin >> A >> B >> H >> M;
  double x, y, ra, rb, r;
  ra = (2 * pi * (H * 60 + M)) / (12 * 60);
  rb = (2 * pi * M) / 60;
  r = abs(rb - ra);
  y = B*sin(r);
  x = abs(A - (B*cos(r)));
  double ans = sqrt(x*x + y*y);
  cout << fixed << setprecision(15) << ans << endl;
  return 0;
}


Measured memory_bytes: 3996
from collections import defaultdict
n=int(input())
l=defaultdict(int)
for i in range(n):
  l1=sorted(list(input()))
  w1="".join(l1)
  l[w1]+=1
count=0
for i in l:
  if l[i]!=1:
    count+=l[i]*(l[i]-1)//2
print(count)

Measured memory_bytes: 18184
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;
    int N = S.size();
    vector<int> ans(N);
    rep(ri, 2) {
        int cnt = 0;
        rep(i, N) {
            if (S[i] == 'R')
                cnt += 1;
            else {
                ans[i] += cnt / 2;
                ans[i - 1] += (cnt + 1) / 2;
                cnt = 0;
            }
        }
        reverse(ALL(ans));
        reverse(ALL(S));
        rep(i, N) {
            if (S[i] == 'L')
                S[i] = 'R';
            else
                S[i] = 'L';
        }
    }
    rep(i, N) cout << ans[i] << " ";
    cout << endl;
    return 0;
}

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    String[] str = in.readLine().split(" ");
    int[] w = new int[n];
    int min = 1000000000;
    int s = 0;
    int t = 0;
    
    for(int i=0; i<n; i++) {
      w[i] = Integer.parseInt(str[i]);
      t+=w[i];
    }

    for(int i=0; i<n; i++) {
      min = Math.min(min,Math.abs(s-t));
      t -= w[i];
      s += w[i];
    }
    System.out.println(min);
  }
}

Measured memory_bytes: 21204
while True:
    x,y,s=map(int,input().split())
    
    if x==0 and y==0 and s==0:
        break
    ans = []
    for i in range(1,s):
        for j in range(1,i+1):
            
            a = i * (100 + x) // 100 + j * (100 + x) // 100
        
            if a == s:
                b = i * (100 + y) // 100 + j * (100 + y) // 100
                ans.append(int(b))
    
    print(max(ans))


Measured memory_bytes: 5600
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(int i=0; i<n; i++)
#define reps(i, s, e) for(int i=s; i<e; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define reprs(i, s, e) for(int i=s-1; i>=s; i--)

int main(){

    int h, w; cin >> h >> w;
    int a[h][w];
    queue<P> q;
    rep(i, h){
        rep(j, w){
            char c; cin >> c;
            if(c == '#'){
                a[i][j] = 0;
                q.push(make_pair(i, j));
            }
            else{
                a[i][j] = -1;
            }
        }
    }


    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    while(!q.empty()){
        P pnow = q.front();
        q.pop();

        int inow = pnow.first;
        int jnow = pnow.second;

        for(int dir=0; dir<4; dir++){
            int inext = inow + dx[dir];
            int jnext = jnow + dy[dir];

            if(inext < 0 || h <= inext) continue;
            if(jnext < 0 || w <= jnext) continue;
            if(a[inext][jnext] != -1) continue;

            q.push(make_pair(inext, jnext));

            a[inext][jnext] = a[inow][jnow] + 1;
        }
    }

    int cnt = 0;
    rep(i, h){
        rep(j, w){
            cnt = max(cnt, a[i][j]);
        }
    }

    cout << cnt;



    return 0;
}

Measured memory_bytes: 12304
n =int(input())
num = [0]*n
tmp = input().split()
L = pow(10,9)+7
for x in range(n):
  num[x] = int(tmp[x])
num.sort()
judge = 1
flg = True
if n%2 == 1:
  judge = 0
  if num[0] != 0:
    flg = False
  else:
    num.pop(0)
prev = -1
count = 0
for i in range(len(num)):
  if prev < 0:
    prev = num[i]
    count += 1
  else:
    if prev == num[i]:
      count += 1
      if count > 2:
        flg = False
        break
    else:
      if count < 2:
        flg = False
        break
      else:
        prev = num[i]
        count = 1
if flg:
  if n%2:
  	print(pow(2,(n-1)//2)%L)
  else:
    print(pow(2,n//2)%L)
else:
  print(0)

Measured memory_bytes: 13812
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
data=[[] for i in range(4)]
w1=wv[0][0]
for u in wv:
    w,v=u
    data[w-w1].append(v)
for i in range(4):
    data[i].sort(reverse=True)
    data[i]=[0]+data[i]
    for j in range(1,len(data[i])):
        data[i][j]+=data[i][j-1]
a=len(data[0])
b=len(data[1])
c=len(data[2])
d=len(data[3])
ans=0
for i in range(a):
    for j in range(b):
        for k in range(c):
            for l in range(d):
                if w1*i+(w1+1)*j+(w1+2)*k+(w1+3)*l<=W:
                    ans=max(ans,data[0][i]+data[1][j]+data[2][k]+data[3][l])
print(ans)

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

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define is insert
#define er erase

using namespace std;

const ll MOD = 1e9 + 7;

int solve();

#define TASK ""

int main()
{
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        //freopen(TASK".in", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    #endif // DEBUG
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

int n;

string s;

ll cnt[30];

ll ans = 1;

int solve()
{
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; ++i)
    {
        cnt[(int)s[i] - (int)'a']++;
    }
    for (int i = 0; i < 30; ++i)
    {
        ans = (ans * (cnt[i] + 1)) % MOD;
    }
    cout << (ans - 1 + MOD) % MOD    << '\n';
    return 0;
}




Measured memory_bytes: 512
// https://atcoder.jp/contests/dp/tasks/dp_e

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define MOD (1e9 + 7)
#define LINF (1e18)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, w, i1, i2;
    ll t, ans = 0;
    cin >> n >> w;
    // dp は重さに対する価値を保存する
    // vector<int> dp(100001, INF);
    map<int, ll> dp, cp;
    dp[0] = 0;
    REP(i, n) {
        cin >> i1 >> i2;
        // 追加用のdpを分ける
        cp = dp;
        for (auto x : dp) {
            ll weight = x.first + i1;
            if (weight <= w) {
                if (cp.count(weight) == 0) {
                    t = x.second + i2;
                } else {
                    t = max(cp[weight], x.second + i2);
                }
                cp[weight] = t;
                ans = max(ans, t);
            }
        }
        dp = cp;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14720
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a+b+c >=22){
        cout << "bust" << endl;
    }else{
        cout << "win" << endl;
    }
    // printf("%d\n", N);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL (1LL<<62) // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
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; }
using namespace std;

int main(){
    // 初期入力
    Init();
    ll n;
    cin >> n;
    vi a(n);
    map<ll, ll> cnt;
    pair<ll, ll> maxNum = {-INFLL, -1}, minNum = {INFLL, -1};
    rep(i, n){
        cin >> a[i];
        cnt[a[i] == 0 ? 0 : a[i]/abs(a[i])]++;
        if(a[i] > maxNum.first) maxNum = make_pair(a[i], i);
        if(a[i] < minNum.first) minNum = make_pair(a[i], i);
    }

    // 操作の記録
    vector<pair<ll, ll>> ans;

    // 正と負の値が混在している場合
    if(cnt[1] != 0 && cnt[-1] != 0){
        // 初期要素のうち、最大値の絶対値が最小値の絶対値より大きい場合は、
        // 全ての要素に最大値を加算することで全て正にできる
        if(abs(maxNum.first) >= abs(minNum.first)){
            for(ll i=0; i<n; i++) if(i != maxNum.second) ans.emplace_back(maxNum.second, i);
            ans.emplace_back(maxNum.second, maxNum.second);
            cnt[1] = n, cnt[-1] = 0, cnt[0] = 0;
        }
        // 最大値の絶対値より最小値の絶対値のほうが大きいまたは等しい場合は、
        // 全ての要素に最小値（負値）を加算することで負or0にできる
        else{
            for(ll i=0; i<n; i++) if(i != minNum.second) ans.emplace_back(minNum.second, i);
            ans.emplace_back(minNum.second, minNum.second);
            cnt[1] = 0, cnt[-1] = n, cnt[0] = 0;
        }
    }

    // 正なら先頭から、負なら末尾から累積和を求める
    if(cnt[1] + cnt[0] == n) for(ll i=0; i<n-1; i++) ans.emplace_back(i, i+1);
    else for(ll i=n-1; i>=1; i--) ans.emplace_back(i, i-1);

    // 答えの出力
    cout << ans.size() << endl;
    for(ll i=0; i<(ll)ans.size(); i++){
        cout << ans[i].first+1 << " " << ans[i].second+1 << endl;
        a[ans[i].second] += a[ans[i].first];
    }
}

Measured memory_bytes: 3668
//	Author : amnptl 
//	   Godbless
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define NeedForSpeed() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MOD (1000000007); // 1e9+7
int main()
{
	NeedForSpeed();
	ll p,s; cin>>p>>s; bool score[p+1] = {false};
	int ac=0,wa=0; map<int,int> m;
	for(int i=0; i<s; i++)
	{
		int x; string res; cin>>x>>res;
		if(res=="AC" && score[x]==false)
			score[x] = true,ac++;
		else if(res=="WA" && score[x]==false)
			wa++,m[x]++;
	}
	for(auto x : m) if(!score[x.first]) wa -= x.second;
	
	cout<<ac<<" "<<wa<<endl;
	return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>
#include <string.h>

#define length 14
#define M 1000003
#define NIL (-1)


int h1(int );
int h2(int );
int Hash(int,int);
int insert(char *);
int find(char *);
int GetKey(char *);
char H[M][length];

int main(){
  int n=0;
  int i=0;
  char cmand[9];
  char word[length];

  for(i=0;i<M;i++){
    H[i][0]='\0';
  }
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%s %s",cmand,word);

    if(cmand[0]=='i') insert(word);

    else {
      if(find(word)) printf("yes\n");
      else printf("no\n");
    }
    
  }

  return 0; 
}

int h1(int key){
  return key % M;
}


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

int Hash(int key,int i){
  return (h1(key)+i*h2(key))%M;
}

int insert(char *T){
  int i=0;
  int j=0;
  int key=0;

  key=GetKey(T);
  
  while(1){

    j=Hash(key,i);

    if(strcmp(H[j],T)!=0 && strlen(H[j])==0){
      strcpy(H[j],T);
      return 0;
    }
    else i=i+1;      
  }
  return 0;
}

int find(char *T){
  int i=0;
  int key=0;
  int j=0;

  key=GetKey(T);
  
  while(1){
    j=Hash(key,i);

    if(strcmp(H[j],T)==0) return 1;

    else if(strlen(H[j])==0) return 0;

    else i=i+1;
  }
  return 0;
}

int GetKey(char *T){
  int i=0;
  int p=1;
  int key=0;
  int number=0;

  for(i=0;i<strlen(T);i++){
    if(T[i]=='A') number=1;
    else if(T[i]=='C') number=2;
    else if(T[i]=='G') number=3;
    else if(T[i]=='T') number=4;

    key += p*number;
    p=p*5;
  }
  return key;
}



Measured memory_bytes: 15424