akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=1e9+7;
//
//
struct poi{
  int X;int Y;int Z;
  bool operator<(const poi&R)const{
    return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
  }
};
//
//
	int w[300000],e[300000];
int main(){
	int N;
	string S;
	cin>>N>>S;
	FOR(i,0,N){
		if(i!=0){
			w[i]+=w[i-1];
		}
		if(S[i]=='W'){
			w[i]++;
		}
	}
	ROF(i,0,N){
		if(i!=N-1){
			e[i]+=e[i+1];
		}
		if(S[i]=='E'){
			e[i]++;
		}
	}
	int ans=INF;
	FOR(i,0,N){
		ans=min(ans,w[i]+e[i]);
	}
	cout<<ans-1<<endl;
	return 0;
}


Measured memory_bytes: 3076
N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)

half = N // 2

Y_n21 = half
Y_n20 = half - 1

for x in X:
    if x < Y[Y_n21]:
        print(Y[Y_n21])
    else:
        print(Y[Y_n20])


Measured memory_bytes: 25620
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int a[SIZE];
LL sum[SIZE],pos[SIZE];
int main(){
    DRII(N,K);
    REP(i,N)RI(a[i+1]);
    REPP(i,1,N+1)sum[i]=a[i]+sum[i-1];
    REPP(i,1,N+1)pos[i]=pos[i-1]+max(0,a[i]);
    LL an=0;
    REPP(i,K,N+1){
        an=max(an,pos[N]-pos[i]+pos[i-K]);
        an=max(an,pos[N]-pos[i]+pos[i-K]+sum[i]-sum[i-K]);
    }
    cout<<an<<endl;
    return 0;
}


Measured memory_bytes: 2176
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        
        int area = a * b;
        int around = 2 * (a + b);
        System.out.println(String.format("%1$s %2$s", area, around));
    }
}


Measured memory_bytes: 26300
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include <cstdlib>
#include<algorithm>
#include <cstdio>
#include <cctype>
using namespace std;
const long long INF=-1000000000;
typedef long long ll;
int N,M,H,W;
ll A,B,D=0,a,b;
string T;
ll F[105][11],P[105][13];
ll hantei(int S){
	int C[100]={};
	if(S==0)return INF;
	int k;
	for(int i=0;i<10;++i){
		k=0;
		if((S>>i&1))k=1;
		for(int j=0;j<N;++j){
			C[j]+=F[j][i]*k;
		}
	}
	ll ans=0;
	for(int i=0;i<N;++i){
		ans+=P[i][C[i]];
	}
	return ans;
}
ll reg(int S,int g){
	if(g==10)return hantei(S);
	return max(reg(S,g+1),reg(S|1<<g,g+1));
}
int main(){
	cin>>N;
	for(int i=0;i<N;++i){
		for(int j=0;j<10;++j){
			cin>>F[i][j];
		}
	}
	for(int i=0;i<N;++i){
		for(int j=0;j<=10;++j){
			cin>>P[i][j];
		}
	}
	cout<<reg(0,0)<<endl;
	return 0;
}


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

int main() {
    int m, n;
    cin >> n >> m;
    string a[n], b[m];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    for (int ai = 0; ai < n; ai++) {
        for (int aj = 0; aj < n; aj++) {
            bool flag = true;
            for (int bi = 0; bi < m; bi++) {
                for (int bj = 0; bj < m; bj++) {
                    int ni = ai + bi;
                    int nj = aj + bj;
                    if (ni >= n || nj >= n) {
                        flag = false;
                        continue;
                    }
                    if (a[ni][nj] != b[bi][bj]) flag = false;
                }
            }
            if (flag) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main()
{
	int n;
	cin >> n;

	vector<int> w(n);
	int w_sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> w.at(i);
		w_sum += w.at(i);
	}

	int tmp_sum = 0;
	int remain = 0;
	int delta = 0;
	int answer = INT_MAX;
	for (int i = 0; i < n; i++)
	{
		tmp_sum += w.at(i);
		remain = w_sum - tmp_sum;
		delta = abs(remain - tmp_sum);
		answer = min(answer, delta);
	}

	cout << answer << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a + b == c + d) cout << "Balanced\n";
	else if (a + b > c + d) cout << "Left\n";
	else cout << "Right\n";

	return 0;
}


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

using namespace std;

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

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


template <class T>
class SegmentTree {
    using Op = std::function<T(T, T)>;

private:
    const Op op;
    const T ID;
    std::vector<T> vec;
    int sz;

public:
    explicit SegmentTree(int _n, Op _op, T _identity) : op(_op), ID(_identity) {
        sz = 1;
        while (sz < _n) sz <<= 1;
        vec.resize(sz * 2, ID);
    }
    void set_value(int _idx, T _val) {
        vec[_idx + sz] = _val;
    }
    template <class RandomIt>
    void set_array(RandomIt _begin, RandomIt _end) {
        std::copy(_begin, _end, vec.begin() + sz);
    }
    void set_array(const std::vector<T>& _newvec) {
        set_array(_newvec.begin(), _newvec.end());
    }
    void build() {
        for (int i = sz - 1; i > 0; i--) {
            vec[i] = op(vec[i * 2], vec[i * 2 + 1]);
        }
    }
    void update(int _idx, T _val) {
        _idx += sz;
        vec[_idx] = _val;
        for (_idx >>= 1; _idx > 0; _idx >>= 1) {
            vec[_idx] = op(vec[_idx * 2], vec[_idx * 2 + 1]);
        }
    }
    T query(int _l, int _r) {
        T l_val = ID, r_val = ID;
        _l += sz, _r += sz - 1;
        for (; _l <= _r; _l >>= 1, _r >>= 1) {
            if (_l & 1) l_val = op(l_val, vec[_l++]);
            if (!(_r & 1)) r_val = op(r_val, vec[_r--]);
        }
        return op(l_val, r_val);
    }
};

using bita = bitset<26>;

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

    ll N;
    cin >> N;
    string S;
    cin >> S;

    SegmentTree<bita> seg(N, [](bita a, bita b) { return a | b; }, 0);

    for (int i = 0; i < N; i++) {
        int d = S[i] - 'a';
        bita u;
        u[d] = true;
        seg.set_value(i, u);
    }

    seg.build();

    ll Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        ll a;
        cin >> a;
        if (a == 1) {
            ll b;
            char c;
            cin >> b >> c;
            --b;
            bita u;
            u[c - 'a'] = true;
            seg.update(b, u);
        }
        else {
            ll b, c;
            cin >> b >> c;
            --b;
            --c;
            bita u = seg.query(b, c + 1);
            ll ans = u.count();
            cout << ans << endl;
        }
    }

    return 0;
}


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

int minus_five(int f, int* money)
{
  if (*money >= f)
  {
    *money -= f;
    return 1;
  }
  return 0;
}

int minus_one(int o, int* money)
{
  int result = *money / o;
  *money = *money - result*o;
  return result;
}

int main(void)
{
  int pay;
  int coin;
  while (true)
  {
    cin >> pay;
    if ( pay == 0 ) break;
    pay = 1000 - pay;
    coin = 0;

    coin += minus_five(500, &pay);
    coin += minus_one (100, &pay);
    coin += minus_five( 50, &pay);
    coin += minus_one ( 10, &pay);
    coin += minus_five(  5, &pay);
    coin += minus_one (  1, &pay);

    cout << coin << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include<iostream>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	int* kinds = new int[M];
	int* kinds_p = new int[M];
	for(int i = 0; i < M; i++) {
		kinds[i] = 0;
		kinds_p[i] = 0;
	}

	int personal_kinds = 0;
	int like_number;
	for (int i = 0; i < N; i++) {
		if (i == 0) {
			cin >> personal_kinds;
			for (int j = 0; j < personal_kinds; j++) {
				cin >> like_number;
				kinds[like_number-1] = 1;
			}
		}
		else {
			for (int j = 0; j < M; j++) {
				kinds_p[j] = 0;
			}
			cin >> personal_kinds;
			for (int j = 0; j < personal_kinds; j++) {
				cin >> like_number;
				kinds_p[like_number-1] = 1;
			}
			for (int j = 0; j < M; j++) {
				kinds[j] *= kinds_p[j];
			}

		}
	}

	int kind_all = 0;
	for (int i = 0; i < M; i++) {
		kind_all += kinds[i];
	}
	cout << kind_all << endl;
}



Measured memory_bytes: 256
h,w = map(int, input().split())

h1,h2 = h//3, h//3+1
w1,w2= min(w//2, w//2+1), max(w//2, w//2+1)
h3,h4 = min(h//2, h//2+1), max(h//2, h//2+1)
w3,w4 = w//3, w//3+1

ans = []

a,b,c = h1*w, (h-h1)*w1, (h-h1)*w2
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = h2*w, (h-h2)*w1, (h-h2)*w2
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = w3*h, (w-w3)*h3, (w-w3)*h4
ans.append(max([a,b,c])-min([a,b,c]))
a,b,c = w4*h, (w-w4)*h3, (w-w4)*h4
ans.append(max([a,b,c])-min([a,b,c]))

ans.append(h)
ans.append(w)

if w%2==0:
  ans.append(abs(h1*w-(h-h1)*w//2))
  ans.append(abs(h2*w-(h-h2)*w//2))

if h%2==0:
  ans.append(abs(w3*h-(w-w3)*h//2))
  ans.append(abs(w4*h-(w-w4)*h//2))
  
if h%3==0 or w%3==0:
  ans.append(0)
  
print(min(ans))

Measured memory_bytes: 3188
import sys
# s = sys.stdin.readlines()
inputs = sys.stdin.readline()
H = sys.stdin.readline()
inputs = inputs.split()
N, K = int(inputs[0]), int(inputs[1])
H = [int(h) for h in H.split()]
H = sorted(H)[::-1]

count = 0
for h in H[K:]:
    count += h

print(count)

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

#define rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1;

const ll INF = 1LL << 60;

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;}

// a^n mod を計算 再帰
ll modpow(ll a,ll n,ll &mod){
  if(!n) return 1;
  ll x = modpow(a,n/2,mod)%mod;
  x *=x;
  if(n%2==1)x*=a;
  return x%mod;
}


int main(){
  int a,b,k;cin>>k>>a>>b;
  int x=k;
  //if(k<a){cout<<"NG";return 0;}
  while(x<=b){
    if(x<=b&&x>=a){cout<<"OK";return 0;}
    x=x+k;
  }
  cout<<"NG";
}


Measured memory_bytes: 3632
main(H,W,i,j){
    for(;scanf("%d %d",&H,&W),H;puts("")){
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                printf("%s%s",i>0&&i<H-1&&j>0&&j<W-1?".":"#",j==W-1?"\n":"");
            }
        }
    }
}

Measured memory_bytes: 1800
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define READ(a) int a; cin >> a;
#define READARR(a, n) int a[(n) + 1]; FOR(i, 1, (n)) {cin >> a[i];}
#define READMAT(a, n, m) int a[n + 1][m + 1]; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define pb(x) push_back(x)
#define vi vector <int>
#define pi pair <int, int>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
int x[11][11], n, d;

double dis (int i, int j)
{
	int s = 0;
	FOR (k, 1, d)
		s += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
	return sqrt(s);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> d;
	FOR (i, 1, n)
		FOR (j, 1, d)
			cin >> x[i][j];
	
	int cnt = 0;
	FOR (i, 1, n)
		FOR (j, i + 1, n)
			if (dis(i, j) == floor(dis(i, j))) cnt++;
	cout << cnt;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <chrono>
#include <random>
#include <unordered_map>
#include <cassert>
#pragma GCC optimize("O3")
#pragma comment(linker, "STACK:36777216")
using namespace std;
using i64 = int64_t;
constexpr i64 MOD = 1e9 + 7;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using vi = vector<i64>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ii = pair<i64, i64>;

int h, w;
int b[500][500];

struct a {
    int y1, x1, y2, x2;
};

vector<a> ans;

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> b[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (b[i][j] % 2) {
                if (j != w - 1) {
                    b[i][j] -= 1;
                    b[i][j + 1] += 1;
                    ans.push_back({i, j, i, j + 1});
                    continue;
                }
                if (i != h - 1) {
                    b[i][j] -= 1;
                    b[i + 1][j] += 1;
                    ans.push_back({i, j, i + 1, j});
                    continue;
                }
            }
        }
    }
    cout << ans.size() << endl;
    for (auto a: ans) {
        cout << a.y1 + 1 << " " << a.x1 + 1 << " " << a.y2 + 1 << " " << a.x2 + 1 << endl;
    }
}


Measured memory_bytes: 5232
#include<stdio.h>
int main(){
    int S;
    int h, m, s = 0;
    scanf("%d", &S);
    h = S / 3600;
    m = (S % 3600) / 60;
    s = (S % 3600) % 60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 2088
n = int(input())
arr = [int(x) for x in input().split()]
q = int(input())

dictA = {}
for i in arr:
    if dictA.get(i): dictA[i] += 1
    else: dictA[i] = 1

summ = sum(arr)

for i in range(q):
    b, c = list(map(int, input().split()))
    if dictA.get(b):
        summ = summ - (dictA[b]*b) + (dictA[b]*c)
        if dictA.get(c): dictA[c] += dictA[b]
        else: dictA[c] = dictA[b]
        del dictA[b]
    print(summ)


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

ll gcd(ll a, ll b){
    if (b)
        return gcd(b, a%b);
    return a;
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

   ll a, b;
    cin >> a >> b;
    cout << a / gcd(a, b) * b << endl;

    if (argc == 2 && atoi(argv[1]) == 123456789)        cerr << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

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

int main() {
  string s;
  cin >> s;
  if (s == "SUN") cout << 7 << endl;
  if (s == "MON") cout << 6 << endl;
  if (s == "TUE") cout << 5 << endl;
  if (s == "WED") cout << 4 << endl;
  if (s == "THU") cout << 3 << endl;
  if (s == "FRI") cout << 2 << endl;
  if (s == "SAT") cout << 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

struct unionfind{
	vector<int> data;
	vector<int> size;
	unionfind(int n){
		for(int i=0;i<n;i++){
			data.push_back(i);
			size.push_back(1);
		}
	}
	
	int find(int x){
		if(data[x]==x)return x;
		return data[x]=find(data[x]);
	}
	
	bool unite(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return false;
		if(size[x]>size[y])swap(x,y);
		data[x]=y;
		size[y]+=size[x];
		return true;
	}
	
	bool check(int x,int y){
		return (find(x)==find(y));
	}
	
	int get_size(int x){
		int X = find(x);
		return size[X];
	}
};

int main(){
	
	int N,M,K;
	cin>>N>>M>>K;
	
	unionfind uf(N);
	vector<vector<int>> E(N);
	
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		uf.unite(a,b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	for(int i=0;i<K;i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	
	for(int i=0;i<N;i++){
		if(i!=0)cout<<' ';
		int ans = uf.get_size(i);
		for(int j=0;j<E[i].size();j++){
			if(uf.check(i,E[i][j]))ans--;
		}
		cout<<ans-1;
	}
	cout<<endl;
	
	return 0;
}


Measured memory_bytes: 8308
import math

n, k = map(int, input().split())
p = 0
for i in range(1,n+1):
    if i >= k:
        p += 1/n
    else:
        l = math.ceil(math.log2(k/i))
        p += (1/n) * ((1/2) ** l)

print(p)


Measured memory_bytes: 3060
#ifdef DBG_MACRO_NO_WARNING
#include <dbg.h>
#endif
#include <bits/stdc++.h>
#define all(c) c.begin(), c.end()
#define isz(c) (int)c.size()

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;

int main(void)
{
    int n;
    cin >> n;

    vi a(n), b(n);
    for (auto &ai : a)
        cin >> ai;
    for (auto &bi : b)
        cin >> bi;

    sort(all(b), greater<int>());

    int l = 0, r = n - 1;

    for (int i = 0; i < n; ++i)
    {
        if (b[i] == a[i])
        {
            if (a[l] != b[i])
            {
                swap(b[l], b[i]);
                ++l;
            }
        }
    }
    for (int i = n - 1; i >= 0; --i)
    {
        if (b[i] == a[i])
        {
            if (a[r] != b[i])
            {
                swap(b[r], b[i]);
                --r;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        if (b[i] == a[i])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    for (int i = 0; i < n; ++i)
    {
        cout << b[i] << " ";
    }
    cout << endl;
    return 0;
}


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

using namespace std;

typedef long long LL;
int n,m,k;
long long ans;

void solve(){
	for (int b=0;b<m;++b){
		for (int c=1;c<n&&b*c<=k*2-2+n*3;++c){
			int r=k*2-2+__gcd(n,b)-b*c;
			ans+=max(0,min(m-1-b,r/n))*(1+(b>0));
			for (int a=r/n+1;a<=r/n+2;++a){
				if (a>0&&a+b<m) ans+=(a*n-__gcd(a,c)-__gcd(n-c,a+b)<=r)*(1+(b>0));
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	solve();
	swap(n,m);
	solve();
	printf("%lld\n",ans*2);
	
	return 0;
}
			

Measured memory_bytes: 3824
s=list(input())
n=len(s)
score=0
g_cnt,p_cnt=1,0
if s[0]=="p":
    score-=1
for i in range(1,n):
    if g_cnt==p_cnt:
        if s[i]=="p":
            g_cnt+=1
            score-=1
        elif s[i]=="g":
            g_cnt+=1
    elif p_cnt<g_cnt:
        if s[i]=="p":
            p_cnt+=1
        elif s[i]=="g":
            p_cnt+=1
            score+=1
print(score)


Measured memory_bytes: 3956
// abc148_c
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}


int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    ll A, B;
    cin >> A >> B;

    ll g = gcd(A, B);
    ll ans = A * B / g;
    print(ans);

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n,k,d[100005];
vector <int> g[100005];
int main()
{
	memset(d,0x3f3f3f3f,sizeof(d));
	cin>>n;
	for (int i=0;i<n-1;++i)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	priority_queue <pair <int,int> > q;
	cin>>k;
	for (int i=0;i<k;++i)
	{
		int v,p;
		cin>>v>>p;
		d[v]=p;
		q.push(make_pair(p,v));
	}
	while (!q.empty())
	{
		int u=q.top().second;q.pop();
		for (int i=0;i<g[u].size();++i)
		{
			int v=g[u][i];
			if (d[v]==0x3f3f3f3f)
			{
				d[v]=d[u]-1;
				q.push(make_pair(d[v],v));
			}
		}
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<g[i].size();++j)
		{
			if (abs(d[i]-d[g[i][j]])!=1)
			{
				cout<<"No\n";
				return 0;
			}
		}
	}
	cout<<"Yes\n";
	for (int i=1;i<=n;++i) cout<<d[i]<<endl;
}

Measured memory_bytes: 7924
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <math.h>
#include <map>
#include<stack>
#include<fstream>

using namespace std;
const long long INF = 1LL << 60;  // どういう意味だろうか

const string write_file("");

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;
}

int main() {
	long long int K, A, B;
	long long int ans = 0;
	long long int k_temp;

	cin >> K >> A >> B;
	k_temp = K;

	if ((B <= A + 2)) {  // 換金の必要性がない場合
		ans = 1 + K;
		cout << ans << endl;
	} else {
		if (K < A + 1) {
			ans = 1 + K;
			cout << ans << endl;
			return 0;
		}

		if (K >= A + 1) {  // 初回のみ
			ans += B;
			k_temp -= A + 1;
		}

		ans += (k_temp / 2) * (B - A);

		ans += (k_temp % 2) * 1;
		cout << ans << endl;

	}

}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
public static class P
{
    public static void Main()
    {
        while (true)
        {
            int n = int.Parse(Console.ReadLine());
            if (n == 0) break;

            bool l = false;
            bool r = false;
            int lastState = 0;
            int res = 0;
            foreach (var item in Console.ReadLine().Split())
            {
                switch (item)
                {
                    case "lu":
                        l = true;
                        break;
                    case "ru":
                        r = true;
                        break;
                    case "ld":
                        l = false;
                        break;
                    case "rd":
                        r = false;
                        break;
                }
                if (l && r && lastState == 0)
                {
                    lastState = 1;
                    res++;
                }
                if (!l && !r && lastState == 1)
                {
                    lastState = 0;
                    res++;
                }
            }
            Console.WriteLine(res);
        }
    }
}


Measured memory_bytes: 15880
N = int(input())
S = input()
group = set()
answer = 0

for x in range(0,N):
    number = 0
    for y in S[:x]:
        group.add(y)
    for y in S[x:]:
        if y in group:
            number += 1
            group.remove(y)
    answer = max(answer,number)
    group.clear 

print(answer)

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;

#define rep(i,n) for(int i=0;i<(n);++i)
#define MAXN 1010
#define linf 8223372036854775808

//d,edge,g
lint d[MAXN];
struct edge{ int to;lint cost; };
vector<edge> g[MAXN];

bool bellmanford(int n,int s){
	d[s]=0;
	rep(i,n){
		rep(v,n){
			for(edge &e:g[v])if(d[v]!=linf&&d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				if(i==n-1&&e.to==n-1)return 1;
			}
		}
	}return 0;
}

int main(){
	int n,m;cin>>n>>m;
	int a,b;lint c;
	fill(d,d+n,linf);
	rep(i,m){
		cin>>a>>b>>c;--a;--b;
		g[a].push_back({b,-c});
	}
	if(bellmanford(n,0))cout<<"inf";
	else cout<<-d[n-1];
	return 0;
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  string s; cin>>s;
  ll n=s.size();
  if(s[n-1]=='s') s+="es";
  else s+='s';
  cout<<s<<endl;
  
}

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

using namespace std;
int main()
{
  string s1,s2;
  cin>>s1;
  cin>>s2;
  
  if(s1.length()>s2.length())
       printf("GREATER");
       
 else if(s1.length()<s2.length()) 
        printf("LESS");
        
else
{
  if(s1>s2)
      printf("GREATER");
  
  else if(s1==s2)
       printf("EQUAL");
  
  
  else
     printf("LESS");
}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<queue>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>

using namespace std;

const int maxn = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef long long ll;

/*
ll modpow(ll a, ll n,int md) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % md;
        a = a * a % md;
        n >>= 1;
    }
    return res;
}
*/

//const int N=200005;
/*
ll N,ans;
int main(){
    cin >> N;
    ll A[N+1];

    for(ll i = 1;i <= N;i++)cin >> A[i];

    for(ll x = 1;x <= N;x++)
        for(ll y = x+A[x]+1;y <= N;y++)
            if(A[x]+A[y] == y - x)ans++;
    printf("%lld\n",ans);
    return 0;
}*/


ll N,K;
int main(){
    cin >> N >> K;
    ll A[N+1];
    for(int i = 1;i <= N;i++)cin >> A[i];
    if(A[1]==1){
        printf("1\n");
        return 0;
    }
    ll now = A[1];
    int x = 1;
    ll B[N+1] = {0};
    B[1] = 1;
    ll KK = K;
    K--;
    for(;( B[now] == 0 && K != 0 );K--){
        B[now] = 1;
        now = A[now];
        x++;
    }

    if(K == 0){
        printf("%lld\n",now);
    }else{
        ll first = now;
        int y;
        now = A[now];
        for(y = 1;now != first;y++)now = A[now];
        KK -= x;
        KK %= y;
        for(;KK != 0;KK--)first = A[first];
        printf("%lld\n",first);
    }

    return 0;
}

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

#define int long long 
#define dou  double 
#define endl "\n"

const int MOD=1e9+7;

void solve()
{
	int x,k,d,ans,x_d,step=0;
	cin >> x >> k >> d;
	x_d = abs(x);

	int a = (x_d)/d;
	x_d -= a*d;
	step = a;

	if(abs(x_d-d)< x_d)
	{
		x_d = abs(x_d-d);
		step++;
	}
	if(k>=step)
	{
		if((k-step)%2 == 0)
			ans = abs(x_d);
		else
			ans = min(x_d+d,abs(x_d-d));
	}
	else
	{	
		x_d = abs(x);
		while(k!=0)
		{
			x_d = x_d - d;
			k--;
		}
		ans = x_d;
	}
	cout << ans << endl;
}

main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	solve();
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int A,B;cin >> A >> B;
  int H = 100, W = 100;
  cout << H SP W << endl;
  vector<vector<char> > maze(H,vector<char>(W,'.'));
  rep(i,H/2) rep(j,W) maze[i][j] = '#';
  bool ischeck = false;
  int count = 0;
  rep(i,H/2-1){
    rep(j,W){
      if(count == A-1){
        ischeck = true;
        break;
      }
      maze[i][j] = '.';
      ++count;
      ++j;
    }
    if(ischeck) break;
    ++i;
  }

  count = 0;
  ischeck = false;
  repp(i,H/2+1,H){
    rep(j,W){
      if(count == B-1){
        ischeck = true;
        break;
      }
      maze[i][j] = '#';
      ++count;
      ++j;
    }
    if(ischeck) break;
    ++i;
  }
  rep(i,H){
    rep(j,W) cout << maze[i][j];
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
 
 
def solve2(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '02468':
            ans += i + 1
    return ans
 
 
def solve5(s):
    ans = 0
    for i, c in enumerate(s):
        if c in '05':
            ans += i + 1
    return ans
 
 
def solve_other(s, p):
    reminders = defaultdict(lambda: 0)
    tmp = 0
    mul = 1
    for c in s[::-1]:
        c = int(c)
        tmp = (tmp + c * mul) % p
        mul = mul * 10 % p
        reminders[tmp] += 1
    reminders[0] += 1
    ans = 0
    for r, cnt in reminders.items():
        ans += cnt * (cnt - 1) // 2
    return ans
 
 

s = input()
n = len(s)
p = 2019


if p == 2:
    print(solve2(s))
elif p == 5:
    print(solve5(s))
else:
    print(solve_other(s, p))

Measured memory_bytes: 9688
#include<stdio.h>
int main(void)
{   int H,W,i,j;
    while(1){
        scanf("%d %d",&H,&W);
        if(H+W==0)break;
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                printf("#");
            }printf("\n");
        }
        
        printf("\n");
    }
return 0;
}



Measured memory_bytes: 2136
// inputに入力データ全体が入る
function Main(input) {
  var ans = ""
  // 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.trim().split("\n");
  var [N] = input[0].split(" ").map((n) => parseInt(n));
  if(N >= 30) {
    console.log('Yes')
  } else {
    console.log('No')
  }





  // console.log(ans)

}
// *この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
// Main(require("fs").readFileSync("./input.txt", "utf-8"));


Measured memory_bytes: 29680
import numpy as np
H,W = map(int,input().split(' '))
X = []
for i in range(H):
  X.append(list(input()))
X = np.array(X)
a = X[:,~np.all(X == '.',axis=0)]
b = a[~np.all(a == '.',axis=1),:]
for i in b:
  print(''.join(i))

Measured memory_bytes: 12508
#include <bits/stdc++.h>
using namespace std;
char enl = '\n';
#define rep(i, from, to) for (int i = from; i < (to); ++i)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<pair<int, int>> vii;



vi graphnodes;
unordered_map<int, int> compress_x;
vector<vi> compressed_neigh;
vi a;
vector<bool> visited;

void dfs(int node) {
    visited[compress_x[a[node]]] = true;
    for (auto child : compressed_neigh[compress_x[a[node]]]) {
        if (visited[compress_x[a[child]]]) continue;
        dfs(child);
    }
}


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

    int n;
    cin >> n;
    a.resize(n);
    vi b(n);
    int sum = 0;
    unordered_map<int, int> compress_y;
    int curindex = 0;
    vi alla(n+1);
    rep(i,0,n) {
        cin >> a[i];
        alla[i] = a[i];
        sum = sum ^ a[i];
        if (compress_x.find(a[i]) == compress_x.end()) {
            compress_x.insert({a[i], curindex});
            compress_y.insert({curindex, a[i]});
            curindex++;
        }
    }
    alla[n] = sum;
    if (compress_x.find(sum) == compress_x.end()) {
        compress_x.insert({sum, curindex});
        compress_y.insert({curindex, sum});
        curindex++;
    }
    vi allb(n);
    rep(i,0,n) {
        cin >> b[i];
        allb[i] = b[i];
        if (compress_x.find(b[i]) == compress_x.end()) {
            cout << (-1) << endl;
            return 0;
        }
    }
    sort(alla.begin(), alla.end());
    sort(allb.begin(), allb.end());

    int offset = 0;
    int mobbad = alla[n];
    for (int i = 0; i < n; i++) {
        while (allb[i] != alla[i+offset]) {
            offset++;
            mobbad = alla[i];
            if (offset > 1) {
                cout << (-1) << endl;
                return 0;
            }
        }
    }
    b.push_back(mobbad);
    a.push_back(sum);

    compressed_neigh.resize(curindex);
    rep(i,0,n+1) {
        if (a[i] != b[i] || i == n) {
            int ca = compress_x[a[i]];
            int cb = compress_x[b[i]];
            compressed_neigh[cb].push_back(i);
            graphnodes.push_back(i);
        }
    }
    a.push_back(sum);
    int graphsize = graphnodes.size();
    // neighs ar compressed_neigh[compress_x[a[graphnodes[i]]]]
    int connected_components = 0;
    visited.resize(curindex);
    for (auto node : graphnodes) {
        if (!visited[compress_x[a[node]]]) {
            connected_components++;
            dfs(node);
        }
    }

    cout << (graphnodes.size()-2+connected_components) << endl;



    
    

    return 0;
}


Measured memory_bytes: 20664
#include <bits/stdc++.h>
typedef long long ll;
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define reptr(i,n) for(int (i)=(n);(i)>=0;--(i))
#define All(X) (x).begin(),(x).end()
using namespace std;
const ll KEY=1e18;

int main() {
  ll a,b,c,k;
  ll tmp1,tmp2,tmp3;
  cin >> a >> b >> c >> k;
  ll x=a-b;
  if(llabs(a-b)>KEY) cout << "Unfair" << endl;
  else {
    if(k%2==0){
      cout << x << endl;
    }else{
      cout << -x << endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
typedef pair<ll,ll> l_l;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back


ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}
ll n;
ll x[10],y[10];
bool b[10];
vector<ll> v;

double dou(){
    double sum=0;
    bool bb=false;
    rep(i,0,n-1){
        if(b[i]==false){
            bb=true;
            b[i]=true;
            v.push_back(i);
            sum+=dou();
            b[i]=false;
            v.pop_back();
        }
    }
    if(bb){
        return sum;
    }else{
        double ans=0;
        rep(i,0,n-2){
            ans+=sqrt((x[v[i]]-x[v[i+1]])*(x[v[i]]-x[v[i+1]])+(y[v[i]]-y[v[i+1]])*(y[v[i]]-y[v[i+1]]));
        }
        return ans;
    }
    
}
double kai(ll i){
    if(i==0){
        return 1;
    }else{
        return kai(i-1)*i;
    }
}

int main(){
    cin>>n;
    rep(i,0,n-1){
        cin>>x[i]>>y[i];
    }
    cout<<setprecision(20)<<dou()/kai(n)<<endl;
    
    
    return 0;
}







Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main(){
  int N;
  cin >> N;
  vector<int> S(N);
  vector<vector<int>> I(3);
  vector<vector<int>> cnt(N,vector<int>(3));
  {
    string s;
    cin >> s;
    map<char,int> R;
    R['R'] = 0;
    R['G'] = 1;
    R['Y'] = 2;
    for(int i = 0; i < N; ++i){
      S[i] = R[s[i]];
      I[S[i]].push_back(i);
      ++cnt[i][S[i]];
    }
    for(int i = 1; i < N; ++i){
      for(int j = 0; j < 3; ++j)
        cnt[i][j] += cnt[i-1][j];
    }
  }
  int r = I[0].size(), g = I[1].size(), b = I[2].size();
  int sz[] = {r,g,b};
  for(int i = 0; i < 3; ++i)
    I[i].push_back(N);
  const int INF = 1e9;
  vector<vector<vector<vector<int>>>> dp(r+1,vector<vector<vector<int>>>(g+1,vector<vector<int>>(b+1,vector<int>(3,INF))));
  for(int i = 0; i < 3; ++i)
    dp[0][0][0][i] = 0;

  for(int i = 0; i <= r; ++i){
    for(int j = 0; j <= g; ++j){
      for(int k = 0; k <= b; ++k){
        for(int l = 0; l < 3; ++l){
          if(dp[i][j][k][l] >= INF) continue;
          for(int m = 0; m < 3; ++m){
            vector<int> tmp = {i,j,k};
            if(tmp[m] >= sz[m]) continue;
            if(l == m) continue;
            int idx = I[m][tmp[m]];
            int c = 0;
            for(int n = 0; n < 3; ++n){
              if(n == m) continue;
              c += max(0,cnt[idx][n] - tmp[n]);
            }
            ++tmp[m];
            auto& lv = dp[tmp[0]][tmp[1]][tmp[2]][m];
            lv = min(lv,dp[i][j][k][l]+c);
          }
        }
      }
    }
  }
  int ans = INF;
  for(int i = 0; i < 3; ++i)
    ans = min(ans,dp[r][g][b][i]);
  if(ans >= INF) ans = -1;
  cout << ans << endl;
}



Measured memory_bytes: 137352
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
#define rep1(i,n) for(int i = 1 ; i <= n ; ++i)
using namespace std;
typedef long long ll;
const ll INFLL = 1e+17;
int n;
ll a[410];
ll sum[410];
ll dp[410][410];
bool f[410][410];
ll rec(int i,int j){
  if(f[i][j]) return dp[i][j];
  f[i][j] = true;
  if(i==j) return dp[i][j] = 0;
  ll res = INFLL;
  rep1(k,j-i+1){
    res = min( res , rec(i+k,j) + rec(i,i+k-1) + sum[j+1] - sum[i] );
  }
  return dp[i][j] = res;
}
int main()
{
  cin >> n;
  rep(i,n) cin >> a[i];

  rep(i,n) rep(j,n) f[i][j] = false;

  sum[0] = 0;
  rep(i,n){
    sum[i+1] = sum[i] + a[i];
  }

  cout << rec(0,n-1) << "\n";
  
  return 0;
}


Measured memory_bytes: 1792
N = int(input())
arr = list(map(int, input().split()))

count=0
flag = False

while True:
    for j in range(N):
            if arr[j]%2 == 0:
                arr[j] /=2
            elif arr[j]%2 != 0:
                flag = True
                break
    count += 1
    if flag == True:
        break

print(count-1)


Measured memory_bytes: 2940
N = int(input())

X = []; Y = []
for i in range(N):
    x, y = [int(i) for i in input().split()]
    X.append(x); Y.append(y);

s = 0
for i in range(N):
    for j in range(N):
        s += ((X[i]-X[j])**2 + (Y[i]-Y[j])**2)**.5

print(s/N)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int main() {
	int n; cin >> n;
	printf("%d\n", n / 3);
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main (void)
{
	int N;
	int T;
	scanf("%d %d", &N, &T);
	int* c;
	int* t;
	c = (int*) malloc(N * sizeof(int));
	t = (int*) malloc(N * sizeof(int));
	int i;
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", c + i, t + i);
	}
	int Error = 0;
	int Min = 0;
	for (i = 0; i < N; i++)
	{
		if (*(t + i) > T)
		{
			Error++;
			continue;
		}
		if (*(c + Min) > *(c + i))
		{
			Min = i;
		}
	}
	if (Error == N)
	{
		printf("TLE\n");
	}
	else
	{
		printf("%d\n", *(c + Min));
	}
}

Measured memory_bytes: 128
import sys
d={' ':'101',"'":'000000',',':'000011','-':'10010001','.':'010001','?':'000001','A':'100101','B':'10011010','C':'0101','D':'0001','E':'110',
'F':'01001','G':'10011011','H':'010000','I':'0111','J':'10011000','K':'0110','L':'00100','M':'10011001','N':'10011110','O':'00101','P':'111',
'Q':'10011111','R':'1000','S':'00110','T':'00111','U':'10011100','V':'10011101','W':'000010','X':'10010010','Y':'10010011','Z':'10010000'}
for e in sys.stdin:
 a=''.join(d[c]for c in e[:-1])
 a+='0'*(-len(a)%5)
 print(''.join("ABCDEFGHIJKLMNOPQRSTUVWXYZ .,-'?"[int(a[i*5:i*5+5],2)]for i in range(len(a)//5)))


Measured memory_bytes: 5604
import sys
X = int(input())
M = int(X/100)
D = X % 100

if M >= 20:
  print(1)
  sys.exit()
else:
  for a in range (0,M+1):
    for b in range (0,M+1-a):
      for c in range (0,M+1-a-b):
        for d in range (0,M+1-a-b-c):
          for e in range (0,M+1-a-b-c-d):
            s = 1 * a + 2 * b + 3 * c + 4 * d + 5 * e
            if s == D:
              print(1)
              sys.exit()
print(0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	if(n%4==0||n%7==0||n%11==0)
	{
		cout<<"Yes"<<endl;
		return 0;
	}
	int p=n;
	while(n>=4)
	{
		n-=7;
		if(n%4==0||n%7==0||n%11==0){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	while(p>=4)
	{
		p-=4;
		if(p%4==0||p%7==0||p%11==0){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
} 


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int N,K,X,Y;
	scanf("%d %d %d %d",&N,&K,&X,&Y);
	if(N < K)
	printf("%d",N * X);
	else printf("%d",K * X + (N - K) * Y);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);


const int INF = INT_MAX;


int main() {
    int n,k; cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    vector<int> dp(n, INF);
    dp[0] = 0;
    rep(i, n) {
        for(int j=1; j <= k; j++) {
            if(i + j < n) {
                dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j] - h[i]));
            } else {
                break;
            }
        }
    }

    cout << dp[n-1] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
bool work(ll a, ll b, ll c, ll d) {
	if (b > a || b > d) return false;
	if (b <= c) return true;
	ll g = __gcd(b, d);
	return b - ((g - a % g == 0) ? g : (g - a % g)) <= c;
}
int main() {
	int T; read(T);
	while (T--) {
		ll a, b, c, d;
		read(a), read(b), read(c), read(d);
		if (work(a, b, c, d)) puts("Yes");
		else puts("No");
	}
	return 0;
}

Measured memory_bytes: 256
n, k = map(int, raw_input().split())


decided = {}

for x in xrange(k):
    a, b = map(int, raw_input().split())
    decided[a - 1] = b - 1

cnt = [[0] * 3 for x in xrange(n)]
dup = [[0] * 3 for x in xrange(n)]

if 0 in decided:
    cnt[0][decided[0]] = 1
else:
    for i in xrange(3):
        cnt[0][i] = 1

for x in xrange(1, n):
    if x in decided:
        i = decided[x]
        for j in xrange(3):
            if i == j:
                cnt[x][i] += cnt[x - 1][j] - dup[x - 1][j]
                dup[x][i] += cnt[x - 1][j] - dup[x - 1][j]
            else:
                cnt[x][i] += cnt[x - 1][j]
    else:
        for i in xrange(3):
            for j in xrange(3):
                if i == j:
                    cnt[x][j] += cnt[x - 1][j] - dup[x - 1][j]
                    dup[x][j] += cnt[x - 1][j] - dup[x - 1][j]
                else:
                    cnt[x][i] += cnt[x - 1][j]

ans = cnt[n - 1][0] + cnt[n - 1][1] + cnt[n - 1][2]
ans %= 10000

print ans

Measured memory_bytes: 4332
#include <algorithm>
#include <vector>
#include <cstdio>
#include <iostream>
#include <math.h>

const double PI = 3.141592653589793;
int main(){
    int x1,y1,x2,y2,n,xf=1,yf=1,x,y;
    scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
    if(x1>x2)std::swap(x1,x2),xf=-1;
    if(y1>y2)std::swap(y1,y2),yf=-1;
    std::vector<std::pair<int,int>> a;
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &x, &y);
        if(x1 <= x && x <= x2 && y1 <= y && y <= y2)a.emplace_back(x*xf,y*yf);
    }
    std::vector<int> b(n,1<<30);
    std::sort(a.begin(),a.end());
    for(auto &e:a){
        n = e.second;
        *std::lower_bound(b.begin(),b.end(),n) = n;
    }
    n = std::lower_bound(b.begin(),b.end(),1<<30)-b.begin();
    printf("%.9f\n",100.0*(x2-x1+y2-y1)-20*n+5*(n+(n>=std::min(x2-x1,y2-y1)+1))*3.14159265359);
}



Measured memory_bytes: 2544