akhauriyash/Code-Regression huggingface dataset:
#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)

Measured memory_bytes: 33296
#include <bits/stdc++.h>
#define lim 300000
using namespace std;
const int mod[3] = {1000000007, 998244353, 1004535809};
int n;
char s[300005];
long long A[3], base[3][600005], lsp, p, suf[3][300005], pre[3];
map<long long, int> cnt[3];
int fsp(long long bs, int p, int mod) {
    int rt = 1;
    while (p) {
        if (p & 1) rt = bs * rt % mod;
        bs = bs * bs % mod, p >>= 1;
    }
    return rt;
}

long long bs(int id, int p) { return base[id][p + lim]; }

int main() {
    for (int t = 0; t < 3; ++t) {
        for (int i = base[t][lim] = 1; i <= lim; ++i)
            base[t][lim + i] = base[t][lim + i - 1] * 250007 % mod[t];
        for (int i = 1, ny = fsp(250007, mod[t] - 2, mod[t]); i <= lim; ++i)
            base[t][lim - i] = base[t][lim - i + 1] * ny % mod[t];
    }
    scanf("%d%s", &n, s + 1), p = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '>') ++p;
        if (s[i] == '<') --p;
        for (int t = 0; t < 3; ++t) {
            if (s[i] == '+') (A[t] += bs(t, p)) %= mod[t];
            if (s[i] == '-') (A[t] += mod[t] - bs(t, p)) % mod[t];
        }
    }

    for (int t = 0; t < 3; ++t) ++cnt[t][suf[t][n + 1] = 0];
    for (int i = n; i > 1; --i) {
        for (int t = 0; t < 3; ++t) suf[t][i] = suf[t][i + 1];
        if (s[i] == '>') --p;
        if (s[i] == '<') ++p;
        for (int t = 0; t < 3; ++t) {
            if (s[i] == '+') (suf[t][i] += bs(t, p)) %= mod[t];
            if (s[i] == '-') (suf[t][i] += mod[t] - bs(t, p)) %= mod[t];
            ++cnt[t][suf[t][i]];
        }
    }

    long long res = min(min(cnt[0][0], cnt[1][0]), cnt[2][0]);
    p = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i] == '>') ++p;
        if (s[i] == '<') --p;
        int tmp = 1000000;
        for (int t = 0; t < 3; ++t) {
            int m = mod[t];
            if (s[i] == '+') (pre[t] += bs(t, p)) %= m;
            if (s[i] == '-') (pre[t] += mod[t] - bs(t, p)) % m;
            --cnt[t][suf[t][i + 1]];
            tmp = min(
                tmp,
                cnt[t][((A[t] - pre[t] - A[t] * bs(t, p) % m) % m + m) % m]);
        }
        res += tmp;
    }
    printf("%lld\n", res);
    return 0;
}


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

signed main(void)
{
	int n, k, ans, mini;
	cin >> n >> k;
	vector<int> h(n), diff(n);
	map<int, int > mp;

	ans = (int)1e9;
	rep(i, n) cin >> h[i];
	sort(h.begin(), h.end());
	rep(i, n - k + 1)
	{
		ans = min(ans, h[i + k - 1] - h[i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define CLEAR(a) memset(a,0,sizeof a)
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define fr freopen("input.txt", "r", stdin);
#define fw freopen("output.txt", "w", stdout);
#define int long long 
typedef long long LL;
typedef pair<int,int> pii;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 5;
int a[MAX], rghtt[MAX], lfft[MAX], pre[MAX];

 main() {
    //fr;
    int n, k;
    cin >> n >> k;
    FOR(i,1,n) cin >> a[i];

    FOR(i,1,n){
        pre[i] = pre[i-1] + a[i];
        lfft[i] = lfft[i-1] + max(0LL, a[i]);
    }

    for(int i=n;i>=1;i--){
        rghtt[i] = rghtt[i+1] + max(0LL, a[i]);
    }
    
    int ret = 0;

    for(int i=1;i<=n-k+1;i++){
        ret = max(ret, lfft[i-1] + max(0LL,pre[i+k-1]-pre[i-1]) + rghtt[i+k]);
    }
    cout << ret;
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

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

    int add = 0, even = 0;
    rep(i,n){
        int x;
        cin >> x;
        if(x % 2) add++;
        else even++;
    }
    if(p == 1 && add == 0){
        cout << 0 << endl;
    }else if(p == 0 && add == 0){
        long long ans = 1;
        rep(i,n){
            ans *= 2;
        }
        cout << ans << endl;
    }else{
        long long ans = 1;
        rep(i,n){
            ans *= 2;
        }
        cout << ans / 2 << endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;

LL n, x;

int main(){
	//freopen("1.in", "r", stdin);
	cin >> n >> x;
	LL len = n;
	LL a = min(n - x, x), b = max(n - x, x);
	while (true){
		len += b / a * 2 * a;
		if (b % a == 0)	 {
			len -= a;
			break;
		}
		LL c = b % a;
		b = a, a = c;
	}
	cout << len << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define M 1000000007

int main() {
	long long int n;
	cin >> n;
	long long int p = 1;
	for (long long int i = 0; i < n; i++) {
		p *= (i+1);
		p %= M;
	}
	cout << p << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
//if(strcmp(s[i],"AC")==0)
//if(s[l]=='#')
int W_Length(char *str){
	int length = 0;
	while(*str++ != '\0')
		length++;
	return length;
}

void swap(int *a, int *b){
  int temp;
  temp=*a;
  *a=*b;
  *b=temp;
}
//swap(&a, &b)

double deg(double theta){//deg to theta
return theta*(2*3.14159265359)/360;
}

int cmp( const void *p, const void *q ) {
    return *(int*)p - *(int*)q;
}//ちいさい順
//qsort(a,n,sizeof(int),cmp);
//char s[n][11]

int cmp_s(const void * left, const void * right)
{
	char *left_char = (char *)left;
  char *right_char = (char *)right;
  return strcmp(left_char, right_char);
}
//qsort(s,n,sizeof(s[0]),cmp_s);


int main (void)
{
	long long int a[85],b[85],c,n,i,buy[85]={0}, sell[85]={0},mon=1000,k=0,m=1,kabu=0;

scanf("%lld",&n);
  scanf("%lld",&a[1]);
  b[1]=a[1];
	for(i=2;i<=n;i++){
scanf("%lld",&a[i]);
      if(a[i-1]==a[i]){
      continue;
      }
      m++;
      b[m]=a[i];
    }
  if(m==1){
  printf("1000\n");
    return 0;
  }
if(b[1]<b[2]){
buy[1]=1;
}
      if(b[m]>b[m-1]){
      sell[m]=1;
      }
  
  for(i=2;i<m;i++){
  if(b[i-1]>b[i]&&b[i+1]>b[i]){
  buy[i]=1;
  }
    
    if(b[i-1]<b[i]&&b[i+1]<b[i]){
    sell[i]=1;
    }
  }
  
  for(i=1;i<=m;i++){
  //printf("%d\n",b[i]);
  if(sell[i]==1){
  mon+=kabu*b[i];
    kabu=0;
  }
    if(buy[i]==1){
    kabu+=mon/b[i];
      mon=mon%b[i];
    }
 // printf("mon=%d kabu=%d, sell %d, buy %d\n",mon, kabu, sell[i], buy[i]);
  }
  
	printf("%lld\n",mon);
return 0;
}


Measured memory_bytes: 1708
x, k, d = map(int, input().split())

if abs(d*k) < abs(x):
    print(abs(x) - abs(d*k))
else:
    pos1 = abs(x)%abs(d)
    pos2 = abs(d) - pos1
    if (k - abs(x)//abs(d))%2 == 0:
        print(pos1)
    else:
        print(pos2)

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

using namespace std;
// typedef unsigned long long ull;


int main(int argc, char const *argv[]) {
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    tx -= sx;
    ty -= sy;
    sx = 0;
    sy = 0;

    string ans;
    for (int i = 0; i < ty; i++) {
        ans += "U";
    }
    for (int i = 0; i < tx; i++) {
        ans += "R";
    }
    for (int i = 0; i < ty; i++) {
        ans += "D";
    }
    for (int i = 0; i < tx; i++) {
        ans += "L";
    }
    ans += "L";
    for (int i = 0; i < ty+1; i++) {
        ans += "U";
    }
    for (int i = 0; i < tx+1; i++) {
        ans += "R";
    }
    ans += "DR";
    for (int i = 0; i < ty+1; i++) {
        ans += "D";
    }
    for (int i = 0; i < tx+1; i++) {
        ans += "L";
    }
    ans += "U";

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int t[2333][2333],b1[2333][2333],b2[2333][2333];
int a[2333][2333],s[2333][2333];
int n,m,q,x,y,xx,yy,sum1,sum2;
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        getchar();
        for(int j=1;j<=m;j++)
        {
            a[i][j]=getchar()-'0';
            s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j])
            {
                if(a[i-1][j])t[i][j]++;
                if(a[i][j-1])t[i][j]++;
            }
            t[i][j]=t[i-1][j]+t[i][j-1]+t[i][j]-t[i-1][j-1];
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]&&a[i-1][j])
            b1[i][j]=1;b1[i][j]+=b1[i][j-1];
        }
    }
    for(int i=2;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[j][i]&&a[j][i-1])
            b2[j][i]=1;b2[j][i]+=b2[j-1][i];
        }
    }
    for(int i=1;i<=q;i++)
    {
        cin>>x>>y>>xx>>yy;
        sum1=s[xx][yy]+s[x-1][y-1]-s[x-1][yy]-s[xx][y-1];
        sum2=t[xx][yy]+t[x-1][y-1]-t[x-1][yy]-t[xx][y-1];
        sum2-=b1[x][yy]-b1[x][y-1];
        sum2-=b2[xx][y]-b2[x-1][y];
        cout<<abs(sum1-sum2)<<endl;
    }
    return 0;
}

Measured memory_bytes: 102144
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> broken(n+1,0);
	vector<long long> dp(n+2,0);
	const int mod = 1000000007;

	for(int i=0; i<m; i++) {
		int a;
		cin >> a;
		broken[a] = 1;
	}

	dp[n] = 1; //初期化
	for(int i=n-1; i >= 0; i--) {
		if(broken[i] == 1) {
			dp[i] = 0; //壊れているところに0をいれる
		} else {
			dp[i] = (dp[i+1] + dp[i+2]) % mod;
		}
	}
	cout << dp[0] << endl;

	// for
	//tableの作成
	// for(int i=0; i<n-1; i++){ for(int j=0; i<2; i++){
	// 		if i+j == a[i] // i+jがa[i]に含まれていた時
	// 		dp[i][j] = i+j;
	// 		cout << a[i] << endl;
	// 	}
	// }
	// vector<list<int>> a(n);
	// a[i].push_back(a[i+1])
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int count_black(int h, int w, vector<vector<char>> &hw, vector<bool> &ignore_h, vector<bool> &ignore_w) {
    int ret = 0;
    rep(i, h) rep(j, w) {
        if (ignore_h[i]) continue;
        if (ignore_w[j]) continue;
        if (hw[i][j] == '#') ++ret;
    }
    return ret;
}

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<char>> hw(h, vector<char>(w));
    rep(i, h) rep(j, w) cin >> hw[i][j];
    int ans = 0;
    rep(i, 1<<(h+w)) {
        vector<bool> ignore_h(h, false);
        vector<bool> ignore_w(w, false);
        rep(j, h+w) {
            if ((i>>j) & 1) {
                if (j < w) {
                    ignore_w[j] = true;
                }
                else {
                    ignore_h[j-w] = true;
                }
            }
        }
        //cout << "w: ";
        //for (auto ww: ignore_w) {
        //    cout << ww << " ";
        //}
        //cout << endl;
        //cout << "h: ";
        //for (auto hh: ignore_h) {
        //    cout << hh << " ";
        //}
        //cout << endl;
        //cout << count_black(h, w, hw, ignore_h, ignore_w) << endl;
        if (count_black(h, w, hw, ignore_h, ignore_w) == k) {
            //cout << i << " " << j << endl;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}


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


using namespace std;

int main(){
  int N;
  cin>>N;
  int A[N];
  for(int i=0;i<N;i++)cin>>A[i];
  int mi=1000000001;
  int ma=0;
  for(int i=0;i<N;i++){
    if(A[i]>ma)ma=A[i];
    if(A[i]<mi)mi=A[i];
  }
  cout<<max((ma-mi),(mi-ma))<<endl;
  return 0;
}


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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF 1e9 + 1
#define INF_LL 1LL<<60
#define ll long long

#define MAX_V 105

#define MAX_N 100
#define MAX_M 100


int main(){
    int n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p;
    cin >> t;
    char dashita[n];

    int ans = 0;

    REP(i, t.size()) {
        if (t[i] == 'r') {
            if(i < k) {
                dashita[i] = 'p';
                ans += p;
            } else {
                if(dashita[i-k] == 'p') {
                    dashita[i] = 'x';
                } else {
                    dashita[i] = 'p';
                    ans += p;                    
                }
            }
        } else if(t[i] == 's') {
            if(i < k) {
                dashita[i] = 'r';
                ans += r;
            } else {
                if(dashita[i-k] == 'r') {
                    dashita[i] = 'x';
                } else {
                    dashita[i] = 'r';
                    ans += r;                    
                }
            }
        } else {
            if(i < k) {
                dashita[i] = 's';
                ans += s;
            } else {
                if(dashita[i-k] == 's') {
                    dashita[i] = 'x';
                } else {
                    dashita[i] = 's';
                    ans += s;                    
                }
            }
        }
    }

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

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

int solvegcd(int p, int q){
  if(p%q ==0) {
    return q;
  }
  return solvegcd(q,p%q);
}

int main() {

  int K;
  cin >> K;
  int ans =0;

  for (int a = 1; a < K+1; a++) {
    for (int b = 1; b < K+1; b++) {
      for (int c = 1; c < K+1; c++) {
        ans += solvegcd(solvegcd(a,b),c);
      }
    }
  }

  cout << ans << endl;

}

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

#define ii pair<int, int>
#define lli long long int
#define ll pair<lli, lli>
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

int main() {
	lli a, b, k, e;
	scanf("%lld %lld %lld", &a, &b, &k);
	e = min(a, k);
	a -= e;
	k -= e;
	e = min(b, k);
	printf("%lld %lld\n", a, b - e);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
  double m[2][2],det,inv[2][2],ans[2],x,y;
  while(cin >>m[0][0]>>m[1][0]>>ans[0]>>m[0][1]>>m[1][1]>>ans[1]){
    det = m[0][0]*m[1][1]-m[1][0]*m[0][1];
    inv[0][0] = m[1][1]/det;
    inv[0][1] = -m[0][1]/det;
    inv[1][0] = -m[1][0]/det;
    inv[1][1] = m[0][0]/det;
    x = inv[0][0]*ans[0]+inv[1][0]*ans[1];
    y = inv[0][1]*ans[0]+inv[1][1]*ans[1];
    printf("%.3lf %.3lf\n",x,y);
  }
  return 0;
}

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

using namespace std;

/*
diameter:
0 W
1 L
2 W
3 W
4 L
..
1 mod 4 is losing
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> adj_list(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        adj_list[a].push_back(b);
        adj_list[b].push_back(a);
    }
    
    vector<vector<int>> down_edges(n);
    function<void (int, int)> find_down_edges = [&](int i, int parent) {
        for (int j : adj_list[i]) {
            if (j != parent) {
                find_down_edges(j, i);
                down_edges[i].push_back(j);
            }
        }
    };
    find_down_edges(0, -1);
    
    function<pair<int, int> (int, int)> diam_and_longest = [&](int i, int parent) {
        int longest_1 = -1, longest_2 = -1;
        int diam = 0;
        for (int j : adj_list[i]) {
            if (j == parent) continue;
            auto p = diam_and_longest(j, i);
            diam = max(diam, p.first);
            int tmp_long = p.second;
            if (tmp_long >= longest_1) {
                longest_2 = longest_1;
                longest_1 = tmp_long;
            } else if (tmp_long >= longest_2) {
                longest_2 = tmp_long;
            }
        }
        diam = max(diam, longest_1 + longest_2 + 2);
        diam = max(diam, longest_1 + 1);
        return make_pair(diam, longest_1 + 1);
    };
    
    int total_diam = diam_and_longest(0, -1).first;
    cerr << "diam = " << total_diam << endl;
    
    if (total_diam % 3 == 1) {
        cout << "Second" << endl;
    } else {
        cout << "First" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 40064
import           Control.Monad
import qualified Data.ByteString.Char8       as BS
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  n <- getInt
  as <- VM.new n
  bs <- VM.new n

  forM_ [1..n] $ \i -> do
    [a, b] <- getIntList
    VM.write as (n-i) a
    VM.write bs (n-i) b

  bs' <- V.freeze bs

  let solve i offset res | i == n    = return res
                         | otherwise = do
                             a <- VM.read as i
                             let b = bs' V.! i
                                 r = (a + offset) `mod` b
                                 r' = if r == 0 then 0 else b - r
                             solve (i+1) (offset+r') (res+r')

  ans <- solve 0 0 0
  print ans

Measured memory_bytes: 29052
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int x, y;
    cin >> x >> y;
    int cost = INT_MAX;
    rep(i, 2) rep(j, 2) {
        int nx = x, ny = y;
        int now = 0;
        if (i) nx = -nx, now++;
        if (j) ny = -ny, now++;
        if (nx <= ny) chmin(cost, now + ny - nx);
    }
    cout << cost << endl;
}


Measured memory_bytes: 3644
using System;
using System.Linq;

namespace Atcoder
{
    class Program
    //AtCoder Beginner Contest 131 B - Bite Eating
    {
        private static void Main(string[] args)
        {
            var nl = Console.ReadLine().Split(' ');
            var n = int.Parse(nl[0]);
            var l = int.Parse(nl[1]);

            int[] tastes = new int[n];

            for (int i = 0; i < n; i++)
            {
                tastes[i] = i + l;
            }
            var min = tastes.OrderBy(a => Math.Abs(a)).First();
            Console.WriteLine(tastes.Sum() - min);
        }
    }
}



Measured memory_bytes: 13396
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned int  ull;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define int ll
#define pll pair<ll, ll> 
#define pdd pair<ld, ld> 
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 1000000007
using namespace std;

ll power(ll x, ll y){  
	if(x == 1 || y == 0)
		return 1;
    ll res = 1;   
    x = x % mod; 
    if (x == 0) 
		return 0;  
    while (y > 0){  
        if (y & 1)  
	        res = (res * x) % mod;  
        y = y >> 1; 
        x = (x * x) % mod;  
    }  
    return res;  
} 
vi pr;
void sieve(int n){ 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime));   
    for (int p=2; p*p<=n; p++){ 
        if (prime[p] == true){ 
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          pr.pb(p); 
} 


signed main(){
	FASTIO
	string s;
	cin >> s;
	if(s.back() == 's'){
		s += "es";
	}
	else{
		s += "s";
	}
	cout << s;
    return 0;
}


Measured memory_bytes: 3652
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>


int cmp(const int *a,const int *b){

return *a > *b ? -1 : *a < *b ? 1 : 0 ;
}
//qsort(pa,n,sizeof(int),(int(*)(const void* ,const void*))cmp);

long long int memo[100];
long long int fib(int n){
  if(n<=1){
    return n;
  }
  else{
    return fib(n-1)+fib(n-2);
  }
}

long long int fib2(int n){
  if(n<=1){
    return n;
  }
  if(memo[n]!=0){
    return memo[n];
  }
    return memo[n]=fib(n-1)+fib(n-2);

}


int main(void){
  char s[30]="abcdefghijklmnopqrstuvwxyz";
  char t;
  scanf("%c",&t);
  int i;
  for(i=0;i<30;i++){
    if(t==s[i]){
      printf("%c",s[i+1]);
      
      return 0;
    }
  }




  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;

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

	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (a[i] == n) {
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}

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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

int N, M;
int dp[100000];
vector< int > g[100000];

int rec(int idx) {
  if(~dp[idx]) return dp[idx];
  int ret = 0;
  for(auto &to : g[idx]) ret = max(ret, rec(to) + 1);
  return dp[idx] = ret;
}

int main() {
  memset(dp, -1, sizeof(dp));
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
  }
  int ret = 0;
  for(int i = 0; i < N; i++) {
    ret = max(ret, rec(i));
  }
  cout << ret << endl;
}



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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int a[11];
bool dfs(int i, int b, int c) {
    if (i == 10) return true;
    if (b < a[i]) {
        if (dfs(i + 1, a[i], c)) return true;
    }
    if (c < a[i]) {
        if (dfs(i + 1, b, a[i])) return true;
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        rep(j, 10) cin >> a[j];
        cout << (dfs(0, 0, 0) ? "YES" : "NO") << endl;
    }
}

Measured memory_bytes: 3076
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

ll dp[64][2];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	ll k;
	cin >> n >> k;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	ll last = 0;
	for(ll i = 0; i <= 50; i++){
		if(k < (1LL << i)){
			last = i - 1;
			break;
		}
	}
	vector<ll> cnt(64, 0LL);
	rep(i, n) for(ll j = 0; j <= 50; j++) if(a[i] & (1LL << j)) cnt[j]++;
	rep(i, 64) rep(j, 2) dp[i][j] = 0LL;
	dp[last][0] = (n - cnt[last]) * (1LL << last); //took it up, so can't take everything
	dp[last][1] = cnt[last] * (1LL << last); //we do not pick it, can be free further
	for(ll i = last - 1; i >= 0; i--){
		dp[i][1] = max(dp[i + 1][1] + (max(n - cnt[i], cnt[i]) * (1LL << i)), ((k & (1LL << i)) ? (cnt[i] * (1LL << i)) + dp[i + 1][0] : 0));
		dp[i][0] = dp[i + 1][0] + (1LL << i) * ((k & (1LL << i)) ? n - cnt[i] : cnt[i]);
	}
	ll ans = 0;
	for(ll i = last + 1; i <= 60; i++) ans += (ll)(cnt[i] * (1LL << i));
	cout << ans + max(dp[0][0], dp[0][1]) << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

const int vy[]={1,0,-1,0};
const int vx[]={0,1,0,-1};

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>> mp(h+2,vector<char>(w+2));
    vector<vector<bool>> visited(h+2,vector<bool>(w+2,true));

    for (int i = 0; i < h; ++i) {
        string s;
        cin>>s;
        for (int j = 0; j < w; ++j) {
            mp[i+1][j+1]=s[j];
            visited[i+1][j+1]=false;
        }
    }

    queue<pair<int,int>> q;
    int nx=1,ny=1;
    long long ans=0;
    int li=0;
    while(true){
        for (int i = li; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if(!visited[i+1][j+1]){
                    q.push(make_pair(i+1,j+1));
                    visited[i+1][j+1]=true;
                    li=i;
                    goto qpushed;
                }
            }
        }
        break;
        qpushed:;
        long long bl=0,wh=0;

        while(!q.empty()){
            ny=q.front().first;
            nx=q.front().second;
            assert(mp[ny][nx]=='#' || mp[ny][nx]=='.');
            if(mp[ny][nx]=='#')++bl;
            else ++wh;
            //cout<<ny<<" "<<nx<<" "<<mp[ny][nx]<<endl;
            q.pop();
            for (int i = 0; i < 4; ++i) {
                if(!visited[ny+vy[i]][nx+vx[i]]&&mp[ny][nx]!=mp[ny+vy[i]][nx+vx[i]]){
                    q.push(make_pair(ny+vy[i],nx+vx[i]));
                    visited[ny+vy[i]][nx+vx[i]]=true;
                }
            }
        }
        ans+=bl*wh;
    }
    cout<<ans<<endl;
    return 0;
}

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

ll a[100000];
ll t[100010];
ll add[100010];
ll s[100010];

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

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}

	for(int i = 0; i < n - 1; i++) {
		if(a[i] < a[i + 1]) {
			int minC = abs(a[i] - a[i + 1]);
			t[0] += minC;
			t[a[i + 1] + 1] += minC;
			add[a[i + 1] + 1] += 1;
			add[a[i] + 1] -= 1;
		}
		else {
			int minC = m + a[i + 1] - a[i];
			int x = minC - (m - 1 - a[i]);
			t[0] += x;
			t[a[i + 1] + 1] += minC;
			add[0] -= 1;
			add[a[i + 1] + 1] += 1;
			add[a[i] + 1] -= 1;
		}
	}

	ll sum = 0, addsum = 0;
	ll ans = 1LL << 60;
	for(int i = 0; i < m; i++) {
		sum += t[i] + addsum;
		addsum += add[i];
		//cerr << sum << endl;
		s[i] = sum;
		ans = min(ans, sum);
	}
	cout << ans << endl;
}


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

int main(void)
{
	char a[200];
	int i;
	
	gets( a );
	
	i = 0;
	
	while( a[i] != '\0' ) {
		a[i] = toupper( a[i] );
		i++;
	}
	
	printf( "%s\n", a );
	
	return 0;
}

Measured memory_bytes: 524
#include <bits/stdc++.h>
#define FOR(i, m, n) for (ll i = m; i < (n); i++)
#define RFOR(i, m, n) for (ll i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
//#define print(ele) cout << (ele) << "\n"
#define print10(ele) cout << fixed << setprecision(10) << (ele) << "\n"

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

void print() { cout << endl; }

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  cout << head;
  if (sizeof...(tail) != 0) cout << " ";
  print(forward<Tail>(tail)...);
}

int main() {
  string s, t;
  cin >> s >> t;
  bool ok = true;
  sort(ALL(s));
  sort(RALL(t));
  ok = s < t ? true : false;
  print(ok ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 256
n, q = [ int(v) for v in input().split() ]
value_list = [ 0 for i in range(n) ]
connect_list = [ [] for i in range(n) ]
for i in range(n-1):
    a, b = [ int(v)-1 for v in input().split() ]
    connect_list[a].append(b)
    connect_list[b].append(a)
for i in range(q):
    c, p = [ int(v)-1 for v in input().split() ]
    value_list[c] += p + 1


serached_list = [ 0 for i in range(n) ]

search_list= connect_list[0]
serached_list[0] = 1
for i in connect_list[0]:
    value_list[i] += value_list[0] 


while search_list != []:
    new_search_list = []
    for i in search_list:
        serached_list[i] = 1
        for j in connect_list[i]:
            if serached_list[j] == 0:
                value_list[j] += value_list[i] 
                new_search_list.append(j)
    search_list = new_search_list
print(*value_list)

Measured memory_bytes: 107084
import itertools
H,W,K=map(int,input().split())
a=[]
ans=0
c=0
for i in range(H):
  t=input()
  c+=t.count('#')
  a.append(list(t))
for i in range(H+1):
  for j in range(W+1):
    for h in itertools.combinations(list(range(H)),i):
      for w in itertools.combinations(list(range(W)),j):
        b=c
        for k in h:
          for m in range(W):
            if a[k][m]=='#':
              b-=1  
        for l in w:
          for n in range(H):
            if a[n][l]=='#':
              b-=1
        for k in h:
          for l in w:
            if a[k][l]=='#':
              b+=1
        if b==K:
          ans+=1
print(ans)

Measured memory_bytes: 9164
#include<iostream>
using namespace std;
#include<string>
#define REP(i,a,b) \
for(int i=a; i<b; i++)
#include<bits/stdc++.h>
#include<algorithm>
#define ll long long int
typedef vector<int> vi;
typedef pair<int,int> ii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define present(c,x) ((c).find(x) != (c).end())

ll findpow(int n)
{
	int count = 0;
	while(n%2 == 0)
	{
		count ++;
		n = n/2;
	}
	return count;
}

int main()
{
	int n;
	cin >> n;
	ll count = 0;
	REP(i,0,n)
	{
		int temp;
		cin >> temp;
		count = count + findpow(temp);
	}
	cout << count;
}

Measured memory_bytes: 256
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
int N,M,A,B,C,T;
V mul(const V &a, const V &b){
	V c(N*N);
	int i=0,j;
	for(;i<N;i++)for(j=0;j<N;j++)c[i*N+j]=(a[slice(i*N,N,1)]*b[slice(j,N,N)]).sum()%M;
	return c;
}
V exp(const V &a, const int n){
	if(n==1)return a;
	if(n&1)return mul(exp(a,n-1),a);
	V b=exp(a,n/2);
	return mul(b,b);
}
V z(){
	V x(N*N);
	int i;
	if(T){
		for(i=0;i<N;i++){
			if(i>0)x[i*N+i-1]=A;
			x[i*N+i]=B;
			if(i<N-1)x[i*N+i+1]=C;
		}
		return exp(x,T);
	}else{
		for(i=0;i<N;i++)x[i*N+i]=1;
		return x;
	}
}
main(){
	int i;
	V s;
	for(;scanf("%d%d%d%d%d%d",&N,&M,&A,&B,&C,&T),N;){
		s.resize(N);
		for(i=0;i<N;i++)scanf("%d",&s[i]);
		const V r=z();
		for(i=0;i<N;i++)printf(i<N-1?"%d ":"%d\n",(r[slice(i*N,N,1)]*s).sum()%M);
	}
}

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

int main(){
  int x;
  cin >> x;
  int a[4];
  for(int i=0; i<4; ++i){
    a[3-i] = x % 10;
    x /= 10;
  }
  for(int i=0; i<8; ++i){
    string s = to_string(a[0]);
    int sum = a[0];
    bool flag = false;
    for(int j=0; j<3; ++j){
      if((i>>j) & 1){
        s += "+";
        sum += a[j+1];
      }
      else{
        s += "-";
        sum -= a[j+1];
      }
      s += to_string(a[j+1]);
    }
    if(sum == 7){
      cout << s << "=7" << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
   public static void main(String[] args){
     Scanner sc = new Scanner(System.in);
     int X = sc.nextInt();
     int Y = sc.nextInt();
     int Z = sc.nextInt();
     
     int A ;
     A=X;
     X=Y;
     Y=A;
     
     int B;
     B=X;
     X=Z;
     Z=B;
     System.out.println(X+" "+Y+" "+Z);
    
   }
}  
  


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

signed main() {
  int N; cin >> N;
  vector<int> H(N);
  for(int i=0; i<N; i++) cin >> H[i];

  for(int i=N-2; i>=0; i--) {
    if(H[i+1] >= H[i]) continue;
    if(H[i+1] != H[i]-1) {
      puts("No");      
      return 0;
    }
    H[i]--;
    if(H[i]<0) {
      puts("No");      
      return 0;
    }
  }
  puts("Yes");
}


Measured memory_bytes: 640
#include <stdio.h>
 int main(void) {
 int k, a, b,s;

 scanf("%d", &k);
 scanf("%d%d", &a, &b);

 s=(b / k) * k;
 if (a <= s) {
 puts("OK");
 } 
 else {
 puts("NG");
 }

 return 0;
}


Measured memory_bytes: 1604
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K = 1;
    cin >> N;
    vec<double> X(N),Y(N);
    for(int i=0;i<N;i++) cin >> X[i] >> Y[i];
    double ans = 1e18;
    
    auto calc = [&](double x,double y){
        vec<double> d(N);
        for(int i=0;i<N;i++){
            double dx = X[i]-x,dy = Y[i]-y;
            d[i] = sqrt(dx*dx+dy*dy);
        }
        sort(d.begin(),d.end(),greater<double>());
        double res = 0;
        for(int i=0;i<K;i++) res += d[i];
        ans = min(ans,res);
        return res;
    };

    auto search_y = [&](double y){
        double l = -1000,r = 1000;
        for(int i=0;i<100;i++){
            double ml = (2*l+r)/3,mr = (l+2*r)/3;
            if(calc(ml,y)<calc(mr,y)) r = mr;
            else l = ml;
        }
        return calc(l,y);
    };

    double l = -1000,r = 1000;
    for(int i=0;i<100;i++){
        double ml = (2*l+r)/3,mr = (l+2*r)/3;
        if(search_y(ml)<search_y(mr)) r = mr;
        else l = ml;
    }
    cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n//i)

    # divisors.sort()
    return divisors


def main():
    N = int(readline())
    target = make_divisors(N)[-2:]
    print(target[0] + target[1] - 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3272
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
using P = pair<int,int>;
using pq = priority_queue<int>;
typedef long long ll;
typedef long double ld;
#define pi 3.14159265358979

int  main()
{
	string s[3];
	rep(i, 3)
		cin >> s[i];
	map<char, int> mp;
	mp['a'] = 0; mp['b'] = 1; mp['c'] = 2;
	vector<queue<char> > q(3);
	rep(i, 3)
	{
		rep(j, s[i].size())
		{
			q[i].push(s[i][j]);
		}
	}
	char f = s[0].front();
	q[0].pop();
	char tmp;
	while (1)
	{
		if (!q[mp[f]].empty())
		{
			tmp = q[mp[f]].front();
			q[mp[f]].pop();
		}
		f = tmp;
		if (q[mp[f]].empty())
		{
			char ans = 'A' + mp[f];
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
	"sort"
)
 
type ByRune []rune

func (r ByRune) Len() int           { return len(r) }
func (r ByRune) Swap(i, j int)      { r[i], r[j] = r[j], r[i] }
func (r ByRune) Less(i, j int) bool { return r[i] < r[j] }

func run() {

	var N int64;
    N = nextInt();
    s := make([]string,N);
    for i := 0 ; i < int(N) ; i++ {
        s[i] = next();
    }
	solve(N, s);

}

func solve(N int64, s []string){	  
	for i, c := range s {
		s[i] = SortStringByCharacter(c)

	}
	
	m := map[string]int{}
	sum := 0

	for _, g := range s {
		v := m[g]
		m[g] = v+1
		sum += v
	}
	Println(sum)
	
}

func StringToRuneSlice(s string) []rune {
	var r []rune
	for _, runeValue := range s {
			r = append(r, runeValue)
	}
	return r
}

func SortStringByCharacter(s string) string {
	var r ByRune = StringToRuneSlice(s)
	sort.Sort(r)
	return string(r)
}
// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int64 {
	a, err := strconv.ParseInt(next(),10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}


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

	int list[30];
	int a;
	int i;

	for(i=0;i<30;i++)list[i]=0;

	while(scanf("%d",&a)!=EOF){
		if(a>30)break;
		list[a-1]=1;
	}

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

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,q;
    string s;
    cin >> n >> s >> q;
    while(q--) {
        int k;
        cin >> k;
        int m = 0,c = 0;
        ll sum = 0;
        ll ans = 0;
        rep(i,k) {
            if(s[i] == 'M') {
                m++;
            } else if(s[i] == 'C') {
                c++;
                sum += m;
            }
        }
        rep(i,n) {
            if(s[i] == 'D') ans += sum;
            else if(s[i] == 'M') {
                m--;
                sum -= c;
            } else if(s[i] == 'C') {
                c--;
            }
            if(i+k >= n) continue;
            if(s[i+k] == 'M') {
                m++;
            } else if(s[i+k] == 'C') {
                c++;
                sum += m;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 4240
#include "bits/stdc++.h"
using namespace std;


int main()
{
	int a, b;
	cin >> a >> b;

	int ans = 0;
	if (a >= 13) {
		ans = b;
	} else if (a >= 6) {
		ans = b / 2;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,a=1,ans=0,b;
  cin >> n;
  while(n>a){
    b = n / a;
    if(n % a == 0){
    b = b - 1;
    }
    ans = ans + b;
    a++;
  }
  cout << ans;
  return 0;
}

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

const int MAX = 1e6+6;

int n , ara[MAX];

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

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

int main(){
    int n, k;
    cin >> n >> k;
    int p[n];
    for(int i = 0; i < n; ++i){
        cin >> p[i];
    }

    sort(p, p+n);

    int ans = 0;
    for(int i = 0; i < k; ++i){
        ans += p[i];
    }

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

Measured memory_bytes: 3640
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>

using namespace std;

int main() {
    stack<int> s;
    string inp;
    while(cin >> inp) {
        int *a;
        string d;
        if(inp == "+") {
            int t = s.top();
            s.pop();
            int u = s.top();
            s.pop();
            s.push(t+u);
            continue;
        } else if(inp == "*") {
            int t = s.top();
            s.pop();
            int u = s.top();
            s.pop();
            s.push(t*u);
            continue;
        } else if(inp == "-") {
            int t = s.top();
            s.pop();
            int u = s.top();
            s.pop();
            s.push(u - t);
            continue;
        } else {
            s.push(stoi(inp));
        }
    }
    cout << s.top() << endl;
    return 0;
}


Measured memory_bytes: 3072
#include<iostream>
using namespace std;
int main()
{	
	int n;
	int a[100] = {0};
	cin >> n;
	for ( int i = 0; i < n; i++)
	{ 
		cin >> a[i];
	}
	
	int sum = 0;
	int temp = 0;

	for (int i= 0; i < n-1; i++ )
	{
		int mini = i;
		for ( int j = i+1; j < n; j++ )
		{
			if ( a[j] < a[mini] )
			{
				mini = j;
			}
		}
		if ( mini != i)
		{
				temp = a[i];
				a[i] = a[mini];
				a[mini] = temp;
				sum++;
		}
		}

	for ( int i= 0; i < n; i++ )
	{
	cout << a[i];
	if ( i < n-1 )
	{
		cout << " ";
	}
	}

	cout << "\n" << sum << endl;

	return 0;
}


Measured memory_bytes: 3084
#include <stdio.h>
int main()
{
	long long int h,t,sum,num;
	long long int i,j;
	
	scanf("%lld %lld",&h,&t);
	
	sum = 0;
	
	for(;t > 0;t--)
	{
		scanf("%lld",&num);
		sum += num;
	}
	
	printf("%s\n",sum >= h?"Yes":"No");
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int M; cin >> M;
    vector<Int> D(M), C(M);
    for (int i = 0; i < M; i++) cin >> D[i] >> C[i];
    Int sum = 0, cnt = 0;
    for (int i = 0; i < M; i++) {
        sum += D[i] * C[i];
        cnt += C[i];
    }
    Int ans = cnt - 1;
    for (;;) {
        Int t = sum / 10;
        if (t == 0) break;
        ans += t;
        sum -= t * 9;
    }
    cout << ans << '\n';
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
using ll = long long;
using ull = unsigned long long;

int main() {
  int a,b,c,k;
  cin>>a>>b>>c>>k;
  int m = max(max(a,b),c);
  cout << a + b + c - m + (m * (1 << k));;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <cassert>
#include <random>
#include <stack>
#include <ctime>
#define REP(i,n) for(long (i)=0;(i)<(n);(i)++)
#define REPI(i,a,b) for(long (i)=(a);(i)<(b);(i)++)
#define INF numeric_limits<double>::infinity()
constexpr long MOD = 1e9 + 7;
using namespace std;
using P = pair<long, long>;
using VI = vector<long>;

long times[101010];

int main() {
    VI ones = {1};
    times[1] = 1;
    for (int i = 6; i < 101010; i *= 6) {
        ones.push_back(i);
        times[i] = 1;
    }
    for (int i = 9; i < 101010; i *= 9) {
        ones.push_back(i);
        times[i] = 1;
    }
    
    REPI(j,1,20) {
        VI as;
        REP(i,101010) {
            if (times[i] == j) {
                as.push_back(i);
            }
        }
        for (auto a: as) {
            for (auto o: ones) {
                if (a + o < 101010) {
                  	if (times[a + o]) {
	                    times[a + o] = min(times[a + o], j + 1);
                    } else {
                      times[a + o] = j + 1;
                    }
                }
            }
        }
    }
    int n;
    cin >> n;
    cout << times[n] << endl;
}


Measured memory_bytes: 1452
#include <iostream>
#include <vector>
using namespace std;
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;
 
int N;
long long ma, mb;
vector<long long> a, b, c;
 
long long dp[51][510][510];
 
int main() {
    cin >> N >> ma >> mb;
    a.resize(N); b.resize(N); c.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i] >> c[i];
    
    for (int i = 0; i < 51; ++i) for (int j = 0; j < 510; ++j) for (int k = 0; k < 510; ++k) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int wa = 0; wa < 500; ++wa) {
            for (int wb = 0; wb < 500; ++wb) {
                if (dp[i][wa][wb] >= INF) continue;
                
                // 使わない
                chmin(dp[i+1][wa][wb], dp[i][wa][wb]);
 
                // 使う
                chmin(dp[i+1][wa+a[i]][wb+b[i]], dp[i][wa][wb] + c[i]);
            }
        }
    }
    long long res = INF;
    for (int wa = 1; wa < 500; ++wa) {
        for (int wb = 1; wb < 500; ++wb) {
            if (wa * mb != wb * ma) continue;
            chmin(res, dp[N][wa][wb]);
        }
    }
    if (res < INF) cout << res << endl;
    else cout << -1 << endl;
}

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

using namespace std;
using namespace __gnu_cxx;

typedef double db;
typedef long long ll;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define F          first
#define S          second
#define pnl        printf("\n")
#define sz(x)      (int)x.size()
#define sf(x)      scanf("%d",&x)
#define pf(x)      printf("%d\n",x)
#define all(x)     x.begin(),x.end()
#define rall(x)    x.rbegin(),x.rend()
#define rep(i, n)  for(int i = 0; i < n; ++i)

const db eps = 1e-9;
const db pi = acos(-1);
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000 * 1000 * 1000 + 7;

int n, a[100100];
int dp[100100];

int solve(int i) {
    if (i == n) return 0;
    int &ret = dp[i];
    if (~ret) return ret;
    ret = solve(i + 1) + abs(a[i] - a[i + 1]);
    if (i + 2 <= n) ret = min(ret, solve(i + 2) + abs(a[i] - a[i + 2]));
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    memset(dp, -1, sizeof dp);
    printf("%d\n", solve(1));
    return 0;
}


Measured memory_bytes: 4096