akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fr freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define mp make_pair
#define F first
#define S second

using namespace std;

const int N = 5e5 + 2;
const int mod = 1e9 + 7;

int main ()
{
	speed;
	ll a,b,c;
	cin>>a>>b>>c;
	ll d=0;
	if (a==5){
		d++;
	}
	if (b==5){
		d++;
	}
	if (c==5){
		d++;
	}
	if (d==2){
		cout<<"YES\n";
	}
	else {
		cout<<"NO\n";
	}
}



Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define REPI(i,a,b) for (ll i=(a);i<(b);i++)
#define REP(i,n) REPI(i,0,n)

typedef long long int ll;

int SURP = 1000000007;

int ceil(int a,int b){
	return (a+b-1)/b;
}

int main(){
	string s;
	cin >> s;
	ll l1 = 0;
	ll l2 = 0;
	ll l = s.length();
	REP(i,l){
		if(i%2 == 1 && s[i] == '0') l1++;
		else if(i%2 == 0 && s[i] == '1') l1++;
	}

	REP(i,l){
		if(i%2 == 1 && s[i] == '1') l2++;
		else if(i%2 == 0 && s[i] == '0') l2++;
	}
	ll ret = min(l1,l2);
	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
int main(void)
{
    int count = 0,count_ten = 0;
    int n,i,ten = 0;
    int field[3];
    char a[8];
    scanf("%d",&n);
    while(n > 0){
        for(i = 0; i < 3; i++) field[i] = 0;
        for(;;){
            scanf("%s",a);
            if(a[0] == 'H' && a[1] == 'O' && a[2] == 'M' && a[3] == 'E' && a[4] == 'R' && a[5] == 'U' && a[6] == 'N'){
                for(i = 0; i < 3; i++) if(field[i] == 1) count_ten++;
                ten = ten + count_ten + 1;
                count_ten = 0;
                for(i = 0; i < 3; i++) field[i] = 0;
            }
            if(a[0] == 'H' && a[1] == 'I' && a[2] == 'T'){
                if(field[2] == 1){
                    ten++;
                    field[2] = 0;
                }
                field[2] = field[1];
                field[1] = field[0];
                field[0] = 1;
            }
            if(a[0] == 'O' && a[1] == 'U' && a[2] == 'T'){
                count++;
                if(count == 3){
                    count = 0;
                    break;
                }
            }
        }
        printf("%d\n",ten);
        ten = 0;
        n--;
    }

    return 0;
}

Measured memory_bytes: 596
f s k n i= if null s then n else if k>(head s) then f (tail s) (head s) (i+1) (i+1) else f (tail s) k n (i+1)
main=do
 n<-getLine
 [t,a]<-map read.words<$>getLine
 h<-map read.words<$>getLine
 let x=map (abs.(+(-a)).(+t).(*(-0.006)))h
 print$f (tail x) (head x) 1 1

Measured memory_bytes: 1404
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
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;
}
map<ll,ll> seen;
vector<int> c={2,3,5};
ll dfs(ll n,vl &v){
    if(n==1)return v[3];
    //if(n==0)return 0;
    if(seen[n]!=0)return seen[n];
   //cout << n <<endl;
    ll ret=INF;
    if(INF/n>v[3])ret=n*v[3];
    rep(i,3){
        if(n%c[i]==0){
            chmin(ret,dfs(n/c[i],v)+v[i]);
        }
        else{
            ll rem=n%c[i];
            if(n/c[i]!=0)chmin(ret,dfs(n/c[i],v)+v[i]+v[3]*rem);
            chmin(ret,dfs(n/c[i]+1,v)+v[i]+v[3]*(c[i]-rem));
        }
    }
    seen[n]=ret;
    return ret;
}
int main(){
    ll t;cin >> t;
    while(t--){
        ll n;cin >> n;
        vl v(4);rep(i,4)cin >> v[i];
        cout << dfs(n,v) <<endl;
        //for(auto p:seen)cout << p.fi <<" " << p.se <<endl;
        seen.clear();
    }
} 

Measured memory_bytes: 4388
#include <stdio.h>

int main() {
  int flag,N,v,k=0;
  int i,j;
  int A[100];

  scanf("%d", &N);

  for ( i = 0; i < N; i++) {
    /* code */
    scanf("%d", &A[i]);
  }

  flag=1;
  while (flag==1) {
    /* code */
  flag=0;
  for ( j = N-1; j >= 1 ; j--) {
    /* code */
    if(A[j]<A[j-1]){

      v=A[j];
      A[j]=A[j-1];
      A[j-1]=v;
      k++;
      flag=1;

    }
  }
}
    printf("%d", A[0]);

  for ( i = 1; i < N; i++) {
    /* code */

   printf(" %d", A[i]);
  }
  printf("\n");
  printf("%d\n", k);

  return 0;

}



Measured memory_bytes: 2048
n = int(input())
w = list(map(int, input().split()))
sum_num = sum(w)
ans = []
temp_f = 0
temp_l = 0
for i in range(n):
  temp_f += w[i]
  temp_l = sum_num - temp_f
  ans.append(abs(temp_f - temp_l))
print(min(ans))

Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int main(){
	while(true){
		int n;
		scanf("%d",&n);
		if(n==0) break;
		int w,h,imos[101][101]={};
		scanf("%d%d",&w,&h);
		rep(i,n){
			int x,y;
			scanf("%d%d",&x,&y);
			imos[x][y]++;
		}
		rep(i,w) rep1(j,h) imos[i+1][j]+=imos[i][j];
		rep(i,h) rep1(j,w) imos[j][i+1]+=imos[j][i];
		int s,t,mx=-1;
		scanf("%d%d",&s,&t);
		rep(i,w-s+1) rep(j,h-t+1){
			mx=max(mx,imos[i+s][j+t]-imos[i][j+t]-imos[i+s][j]+imos[i][j]);
		}
		printf("%d\n",mx);
	}
	return 0;
}

Measured memory_bytes: 1056
s = [ord(i) for i in input()]
K = int(input())

ret = []
for c in s[:-1] :
    if c == 97 :
        ret.append('a')
        continue
        
    if c + K > 122 :
        ret.append('a')
        K -= 123 - c
    else :
        ret.append(chr(c))
        
K %= 26
ret.append(chr((s[-1] + K - 97) % 26 + 97))
        
print(''.join(ret))

Measured memory_bytes: 48692
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class era{
public:
    era(string s, int b, int l){
        name = s;
        begin = b;
        len = l;
    }

    string name;
    int begin;
    int len;
};

int main(){
    int n,q;
    while(cin >> n >> q && n+q!=0){
        vector<era> v;
        string str;
        int len,begin,query;
        for(int i=0;i<n;i++){
            cin >> str >> len >> begin;
            v.push_back(era(str, begin-len+1, len));
        }
        for(int i=0;i<q;++i){
            bool isok = false;
            cin >> query;
            for(int j=0;j<n;++j){
                if(v[j].begin <= query &&
                   query < v[j].begin + v[j].len){
                    isok = true;
                    cout << v[j].name << " " << query - v[j].begin+1 << endl;
                }
            }
            if(!isok) cout << "Unknown" << endl;
        }
    }
}

Measured memory_bytes: 0
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main() {
    char c;
    cin >> c;
    if(islower(c))
        cout << "a" << endl;
    else
        cout << "A" << endl;
    return 0;
}

Measured memory_bytes: 3036
import java.util.*;

public class Main {
  
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        int ans = 0;
        for (int a = 1; a <= k; a++) {
            for (int b = 1; b <= k; b++) {
                for (int c = 1; c <= k; c++) {
                    ans += gcd(gcd(a,b),c);
                }
            }
        }
		System.out.println(ans);
    }

    public static int gcd(int num1,int num2) {
        if(num2==0) return num1;
        else return gcd(num2,num1%num2);
    }
}


Measured memory_bytes: 35668
let readIntArray _ =
    stdin.ReadLine().Split(" ") |> Array.map int

let toCheckpoint checkpoints [| x; y |] =
    checkpoints
    |> Array.minBy (fun (_, [| a; b |]) -> abs (x - a) + abs (y - b))
    |> fst
    |> (+) 1
    |> string

()
|> readIntArray
|> fun [| n; m |] ->
    let students = [| 1 .. n |] |> Array.map readIntArray

    let checkpoints =
        [| 1 .. m |]
        |> Array.map readIntArray
        |> Array.indexed

    students
    |> Array.map (toCheckpoint checkpoints)
    |> String.concat "\n"
    |> printfn "%s"


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

using namespace std;
#define ll long long 
ll MOD=7+(ll)1e9;

int main() {
ll n;

  cin >> n;
    ll ans = 1e18;
    for(int i=1;i<= 1010101;i++) 
    if (n % i == 0) 
     ans=min(ans, i + n / i - 2);
    cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define oo (int)1e9
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5;


int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    priority_queue<pair<int, int> > pq;
    for(int i = 0 ; i < n ; ++i){
        int x;
        scanf("%d", &x);
        pq.emplace(x - (x / 2), x);
    }
    while(pq.size() && m--){
        auto p = pq.top();
        pq.pop();
        int x = p.second;
        x /= 2;
        if(!x)continue;
        pq.emplace(x - (x / 2), x);
    }
    ll ans = 0;
    while(pq.size()){
        auto p = pq.top();
        pq.pop();
        ans += (1LL * p.second);
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 1400
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i)
#define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i)

template <typename _typer> inline _typer read() {
	_typer init = 0;
	char ch = getchar(), k = 0;
	for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
	for ( ; isdigit(ch); ch = getchar())
		init = (init << 3) + (init << 1) + (ch ^ 48);
	return k ? -init : init;
}
const ll N = 15, INF = 1e9;

/*******************************************************************************
 *
 *
 *
 ******************************************************************************/

int n, m;
int A[N][N];

bool Check(int x, int y) {
	ll res = 0;
	rep (i, 1, m) {
		res += (A[x][i] - A[y][i]) * (A[x][i] - A[y][i]);
	}
	if ((int) sqrt(res) * (int) sqrt(res) == res) return true;
	else return false;
}

int main() {
	n = read<int>(), m = read<int>();
	rep (i, 1, n) rep (j, 1, m) A[i][j] = read<int>();
	int Ans = 0;
	rep (i, 1, n) rep (j, i + 1, n) {
		if (Check(i, j)) ++Ans;
	}
	cout << Ans << endl;
	return 0;
}



Measured memory_bytes: 256
import math
A, B = map(int, input().split())
se = set()


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

    divisors.sort()
    return divisors


a = (set(make_divisors(A)))
b = (set(make_divisors(B)))
tmp = list(a & b)


def is_prime(n):
    if n == 1:
        return True

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


ans = sum([is_prime(i) for i in tmp])
print(ans)


Measured memory_bytes: 5132
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    int X, Y, Z;
    cin >> X >> Y >> Z;

    int re = X - Z;
    int ans = re / (Y+Z);
    int amari = re % (Y+Z);

    if(amari >= Y+Z){
        cout << ans+1 << endl;
    }else{
        cout << ans << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
	int  a, b;
	cin >> a >> b;
	vector<string> A;
	string s;
	for(int i = 0; i < b; ++i){
		s += to_string(a);
	}
	A.push_back(s);
	s = "";
	for(int i = 0; i < a; ++i){
		s += to_string(b);
	}
	A.push_back(s);
	sort(A.begin(), A.end());
	cout << A[0] << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,ans,cur,f[N],g[N];
char ch[N];
set<int> e[N];
void del(int x){
	for (auto y : e[x]){
		e[y].erase(x);
		if ((ch[y]=='B')&&(e[y].size()==1)) del(y);
	}
	e[x].clear();
}
void dfs(int x,int fa){
	ans+=e[x].size();
	int r=(ch[x]=='B')==(e[x].size()&1);
	if (r) ans++;
	f[x]=(r^1)-r-1;
	g[x]=0;
	for (auto y : e[x])
	if (y!=fa) {
		dfs(y,x);
		cur=min(cur,f[x]+g[y]);
		cur=min(cur,f[y]+g[x]);
		f[x]=min(f[x],f[y]+(r^1)-r-1);
		g[x]=min(g[x],g[y]+(r^1)-r-1);
	}
}
void getans(int x){
	dfs(x,0);
	ans+=cur;
}
int main(){
	n=read();
	for (int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].insert(v);
		e[v].insert(u);
	}
	scanf("%s",ch+1);
	for (int i=1;i<=n;i++)
	if ((ch[i]=='B')&&(e[i].size()==1)) del(i);
	for (int i=1;i<=n;i++)
	if (ch[i]=='W') {getans(i);break;}
	printf("%d\n",ans);
	return 0;
}

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


int main(){
	while(true){
		int n;
		cin>>n;
		
		if(n==0)
			break;
		
		char c[100];
		
		for(int i=0;i<n;i++){
			cin>>c[i];
		}

		int cnt[26]={0};
			
		for(int i=0;i<n;i++){
			cnt[(int)(c[i]-'A')]++;
			
			int max1 =-1;
			int max2 =-1;
		
			for(int j=0;j<26;j++){
				if(cnt[j]>max1){
					max2 = max1;
					max1 = cnt[j];
			}else if(cnt[j]>max2){
				max2 = cnt[j];
			}
		}

		if(max1-max2>n-(i+1)){
			for(int j=0;j<26;j++){
				if(cnt[j]==max1){
					cout<<(char)(j+'A')<<' ';
					break;
				}
			}
			cout<<(i+1)<<endl;
			break;
		}

		if(i==n-1){
			cout<<"TIE"<<endl;
			break;
		}
		}
	}
	return 0;
}

Measured memory_bytes: 3092
// writer: w33z8kqrqk8zzzx33
#include <bits/stdc++.h>
#include <atcoder/convolution>
using namespace std;

#define iter(i, a, b) for(int i=(a); i<(b); i++)
#define rep(i, a) iter(i, 0, a)
#define rep1(i, a) iter(i, 1, (a)+1)
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll=long long;
using pii=pair<int, int>;
//#define int ll
const int MOD = 1000000007;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m; cin >> n >> m;
	vector<int> a(n), b(m);
	rep(i, n) cin >> a[i];
	rep(i, m) cin >> b[i];
	vector<int> c = atcoder::convolution(a, b);
	for(int& k:c) cout << k << ' ';
}


Measured memory_bytes: 19076
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){

    int N, M;
    cin >> N;
    vector<int> T(N);
    for(int i = 0; i < N; i++) cin >> T[i];
    cin >> M;
    vector<int> P(M), X(M);
    for(int i = 0; i < M; i++) cin >> P[i] >> X[i];
    vector<long long> res(M);
    long long sum  = 0;
    for(int i = 0; i < N; i++) sum += T[i]; 
    for(int i = 0; i < M; i++) res[i] =sum - (T[P[i] - 1] - X[i]);
    for(int i = 0; i < M; i++) cout << res[i] << endl;
    return 0;
}


Measured memory_bytes: 256
# 初期入力
import sys
input = sys.stdin.readline
a = list(map(int, input().split()))
a+= [0]*(10**6 +1)
i=0
while True:
   
    if a[i] %2 ==0:
        a[i+1] =a[i]//2
    else:
        a[i+1] =a[i] *3 +1
    if a[i+1] in a[:i]:
        print(i+1+1)
        break
    i +=1

Measured memory_bytes: 24548
import java.util.Scanner;

public class Main
{
	static public int ans100 = -1;
	static public int ans10 = -1;
	static public int ans1 = -1;
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();
		scan.close();

		String[] substr = str.split(" ", 0);
		int a = Integer.parseInt(substr[0]);
		int b = Integer.parseInt(substr[1]);

		int ans = -1;
		for (int i = 1; i< 2000; i++) {
			int aa = (int)(i * 0.08);
			int bb = (int)(i *0.1);
			if (aa == a && bb == b)  {
				ans = i;
				break;
			}
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 24148
S = input()
T = input()
N = len(S)
M = len(T)

for i in range(1,N-M+2):
  count = 0
  for j in range(1,M+1):
    if S[N-i-j+1] == T[M-j] or S[N-i-j+1] == "?":
      count += 1
    else:
      break
  if count == M:
    S = S[:N-i-M+1]+T+S[N-i+1:]
    S = S.replace("?","a")
    print(S)
    exit()
else:
  print("UNRESTORABLE")


Measured memory_bytes: 3064
import java.util.*;

public class Main{
    //Favorite Sound
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
        System.out.println(helper(a, b, c));
        sc.close();
    }

    public static int helper(int a, int b, int c) {
        return b / a > c ? c : b / a;
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll b[n];
  //  ll a[n];
    for(ll i=0;i<n-1;i++)
    {
        cin>>b[i];
    }
    ll m=b[n-2],s=0;
    for(ll i=n-3;i>=1;i--)
    {
        // if(b[i]<m && )
        // m=b[i];
        if(b[i+1]>b[i])
        s=s+b[i];
        else 
        s=s+b[i+1];
        
      //  cout<<s<<endl;
      
    }
    s=s+b[0]+b[0]+b[n-2];
    
    if(n>2 && b[0]>b[1])
    s=s-b[0]+b[1];
    if(n==2)
    s=2*b[0];

    cout<<s<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define endl '\n'
#define D(x) cout << #x << " = " << (x) << endl;

class disjointset {
public:
  int n;
  vector<int> parent, cnt;

  disjointset(int _n) {
    n = _n;
    parent.resize(n);
    cnt.resize(n);
    makeset();
  }

  void makeset() {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
      cnt[i] = 1;
    }
  }

  int findset(int x) {
    if (parent[x] != x) parent[x] = findset(parent[x]);
    return parent[x];
  }

  int count(int x) {
    return cnt[findset(x)];
  }

  void join(int x, int y) {
    int x_set = findset(x);
    int y_set = findset(y);

    if (x_set != y_set) {
      int total = cnt[x_set] + cnt[y_set];
      cnt[x_set] = total;
      cnt[y_set] = total;
    }

    parent[x_set] = y_set;
  }
};

int main() { IO;
  int n, m;
  cin >> n >> m;

  vector<pair<int, int>> edges(m + 1);
  for (int i = 1; i <= m; ++i) {
    cin >> edges[i].first >> edges[i].second;
  }

  disjointset ds(n + 1);
  vector<long long> ans(m + 1);

  for (int i = m; i > 0; --i) {
    int a = edges[i].first;
    int b = edges[i].second;

    if (ds.findset(a) == ds.findset(b)) {
      ans[i] = 0;
    } else {
      ans[i] = 1LL * ds.count(a) * ds.count(b);
      ds.join(a, b);
    }
  }

  for (int i = 1; i <= m; ++i) {
    ans[i] += ans[i - 1];
    cout << ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 3712
// https://atcoder.jp/contests/abc178/tasks/abc178_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};
mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
mint operator+(mint a, mint b) {
    int x = a.n + b.n;
    return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
    int x = a.n - b.n;
    return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
    for (int i = I_.size(); i <= n; i++) {
        I_.push_back(I_[MOD % i] * (MOD - MOD / i));
        F_.push_back(F_[i - 1] * i);
        R_.push_back(R_[i - 1] * I_[i]);
    }
}

mint I(int n) {
    check_fact(abs(n));
    return n >= 0 ? I_[n] : -I_[n];
}
mint F(int n) {
    check_fact(n);
    return n < 0 ? 0 : F_[n];
}
mint R(int n) {
    check_fact(n);
    return n < 0 ? 0 : R_[n];
}
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

void solve() {
    int N;
    cin >> N;
    mint ans = 0;
    // 3個ずつをiグループ作成し、残ったものを敷居(i-1)個で分割
    // 残り2個を4グループに分ける場合は敷居3つ「○|○||」
    FOR(i, 1, N / 3 + 1) { ans += C(N - i * 3 + i - 1, i - 1); }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


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

using namespace std;

int main(int argc, char const* argv[])
{
  string s;
  cin >> s;
  string even, odd;
  for (int i = 0; i < s.length(); i++) {
    if(i%2==0) even.push_back(s[i]);
    else odd.push_back(s[i]);
  }
  int evenzero = count(even.begin(), even.end(), '0');
  int evenone = count(even.begin(), even.end(), '1');
  int oddzero = count(odd.begin(), odd.end(), '0');
  int oddone = count(odd.begin(), odd.end(), '1');
  cout << min(evenzero+oddone, evenone+oddzero) << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>                                                             
#include <cstring>                                                              
                                                                                
using namespace std;                                                            
                                                                                
int main(void) {                                                                
  int n, m, a;                                                                  
  int G[1001][101];                                                             
                                                                                
  while(true){                                                                  
    cin >> n >> m >> a;                                                         
    if (n+m+a==0) {                                                             
      break;                                                                    
    }                                                                           
    memset(G,0,sizeof(G));                                                      
                                                                                
    for (int i=0; i<m; i++) {                                                   
      int h ,p ,q;                                                              
      cin >> h >> p >> q;                                                       
      G[h][p]=q;                                                                
      G[h][q]=p;                                                                
    }                                                                           
    for (int i=1000; i>=0; i--) {                                               
      if (G[i][a]!=0) {                                                         
        a=G[i][a];                                                              
      }                                                                         
    }                                                                           
    cout << a << endl;                                                          
  }                                                                             
                                                                                
  return 0;                                                                     
}                            

Measured memory_bytes: 3348
#include <stdio.h>

int main (void){

	int a,b,c;
	int yakusu = 0;
	scanf("%d %d %d",&a,&b,&c);
	
	while(a<=b){
		if(c%a == 0){
			yakusu++;
		}
		a++;
	}
	printf("%d\n",yakusu);
	return 0;
}

Measured memory_bytes: 596
using System;
class Program
{
    public static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');
        int a, b;
        a = int.Parse(str[0]);
        b = int.Parse(str[1]);
        bool f = (a % 3 == 0) || (b % 3 == 0) || ((a + b) % 3 == 0);
        Console.WriteLine(f ? "Possible" : "Impossible");
    }
}

Measured memory_bytes: 13140
n = int(input())
a = list(map(int,input().split()))
s = sum(a)
a.sort()
b = 1
for i in a:
  b |= b<<i
  
b &= 2**(s+1)-2**((s-1)//2)
while True:
  t = b&(-b)
  T = t.bit_length()-1
  if (s+1)//2 <= T <= s:
    print(T)
    break
  b ^= t

Measured memory_bytes: 11552
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma warning(disable:4996)
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <set>
#include <map>
#include <iomanip> 
#include <ctime>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

const double PI = 3.14159265358979323846;
const int MAX = 1e10;
const int MOD = 1e9+7;

const int MAX_N = 100005;



int main(int argc, char *args[]) {
	int n, k; cin >> n >> k;
	vector<ll> h(n);
	rep(i, n) cin >> h[i];
	sort(h.begin(), h.end());
	ll sum = 0;
	for (int i = 0; i < n - k; i++) {
		sum += h[i];
	}
	cout << sum << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    int n,max=1;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=7;j++){
            if(pow(2,j) == i){
                max = i;    
            }
        }
    }
    cout << max << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0; i<N; i++)

using namespace std;

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

  double aa=0;
  double t=0;
  rep(i,n){
  	aa = (double)1 / a[i];
  	t += aa;
  }

  double ans=0;
  ans = (double) 1 / t;

  printf("%lf\n", ans);
  //cout << fixed;
  //cout << setprecision(10)  << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<deque>

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e8;

using namespace std;

#define vvint(vec,n,m,l) vector<vector<int>> vec(n,vector<int>(m,l));
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>;
#define pint pair<int,int>;
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")


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

	int n;
	cin >> n;
	vector<int> a(n + 1, 0);
	int ans = 0;
	rep(i, n)
	{
		cin >> a[i];
	}

	int val = INF;

	for (int l = 0; l < n;)
	{
		if (a[l] == 0)
		{
			l++;
			continue;
		}
		for (int r = l; a[r]!=0; r++)
		{
			val = min(a[r], val);
			if (a[r+1] == 0)
			{
				ans += val;
				for (int i = l; i <= r; i++)
				{
					a[i] -= val;
				}
			}
		}
	}

	cout << ans << endl;

}

Measured memory_bytes: 256
// Try AtCoder
// author: Leonardone @ NEETSDKASU

fn main() {
    let mut stdin = String::new();
    std::io::Read::read_to_string(
        &mut std::io::stdin(),
        &mut stdin).unwrap();
    let mut stdin = stdin.split_whitespace();
    let mut get = || stdin.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let a = get!();
    let b = get!();
    let c = get!();
    let d = get!();
    let cd = c / gcd(c, d) * d;
    let fc = if a % c == 0 { 1 } else { 0 };
    let fd = if a % d == 0 { 1 } else { 0 };
    let fcd = if a % cd == 0 { 1 } else { 0 };
    let mut ans = b - a + 1;
    ans -= b / c - (a - fc) / c;
    ans -= b / d - (a - fd) / d;
    ans += b / cd - (a - fcd) / cd;
    
    println!("{}", ans);
}

fn gcd(a: i64, b: i64) -> i64 {
    if a == 0 {
        b
    } else {
        gcd(b % a, a)
    }
}

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

int main() {
  int N;
  cin >> N;
  int member[N+5];
  memset(member, 0, sizeof member);
  for (int i = 1; i < N; ++i) {
    int tmp;
    cin >> tmp;
    ++member[tmp];
  }
  for (int i = 1; i <= N; ++i) {
    cout << member[i] << '\n';
  }
  return 0;
}

Measured memory_bytes: 4412
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
  string s;
  int b1=0,b2=0,w1=0,w2=0;
  cin>>s;
  for(int i=0;i<s.size();i+=2){
    if(s[i]=='1'){
      w1++;
    }else{
      b2++;
    }
  }
  for(int i=1;i<s.size();i+=2){
    if(s[i]=='0'){
      b1++;
    }else{
      w2++;
    }
  }
  cout<<min(b1+w1,b2+w2)<<"\n";
    
      

  return 0;
}


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

int main(){
	int h,w;
	while(1){
		scanf("%d %d",&h,&w);
		if(h==0 && w==0) break;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if((i+j)%2==0) printf("#");
				else printf(".");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1000
// Created by: WeirdBugsButOkay
 
#include <bits/stdc++.h>
 
#define ll long long
#define ld long double
#define ff first
#define ss second
#define PI 3.14159265358979323846
#define endl '\n'
 
using namespace std;
 
void solve()
{
	ll n;
	cin >> n;
	ll p = 26, q = 0, cnt = 1;
	while(q + p < n)
	{
		q += p;
		p *= 26;
		cnt++;
	}
	ll v = n - q;
	//cout << v << endl;
	v--;
	string ans;
	for(ll i = 0; i < cnt; i++)
	{
		ans = (char)(v % 26 + 'a') + ans;
		v /= 26;
	}
	cout << ans << endl;
}
 
int main()
{
	int q = 1;
	//scanf("%d", &q);
	for(int i = 1; i <= q; i++)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3612
#include <iostream>

using namespace std;

int main() {
  //input
  int a;
  cin >> a;
  int b;
  cin >> b;
  int t;
  cin >> t;

  int num = t / a;

/*
  cout << a << endl;
  cout << b << endl;
  cout << t << endl;
  cout << num << endl;
*/

  //solve
  int ans = num * b;


  // output
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;

int N;

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

	cin >> N;

	REP(i, N-1) {
		FOR(j, i + 1, N) {
			int ans;

			int k = 0;

			while (1) {
				if ((i&(1<< k)) != (j&(1<< k))) {
					//cout << i << " " << j << endl;
					ans = k + 1;
					break;
				}
				k++;
			}

			cout << ans << " ";
		}
		cout << endl;
	}
	

	return 0;
}



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

typedef long long LL;
void solve(long long N, long long K, std::vector<long long> h) {
  sort(h.begin(), h.end());
  LL minim = 1000000;
  minim *= minim;

  for (int i = 0; i + K <= N; i++) {
    minim = min(minim, h[i + K - 1] - h[i]);
  }

  cout << minim << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> h(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &h[i]);
  }
  solve(N, K, std::move(h));
  return 0;
}


Measured memory_bytes: 1024
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,K=map(int,input().split())
sunuke=[0 for i in range(N)]
for k in range(K):
    d=int(input())
    A=list(map(int,input().split()))
    for i in range(d):
        sunuke[A[i]-1]+=1
#print(sunuke)
print(len([i for i in sunuke if not i]))


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

int main(){
	ll x, y, i=0;
	cin>>x>>y;
	while(true){
		if(x>y) break;
		x=x<<1;
		i++;
	}
	cout<<i<<endl;
	return 0;
}

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


int main(){

 long long int N;
  scanf("%lld",&N);

/*
  char A[];
  scanf("%s",A);
  */

  /*
  int A[N];
  int i;
  for(i=0;i<N;i++){
   scanf("%d",&A[i]);
   }
  */
long long int A;
A = 100;
long long int i;
i=0;
while (A < N){
A = A +(long long int)(A*0.01);
i+=1;
}
printf("%lld",i);







 return(0);
 }


Measured memory_bytes: 1732
import java.util.Scanner;
public class Main
{
  public static void main (String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int p = sc.nextInt();
    int q = sc.nextInt();
    int result = 0;
    
    for(int i = 0; i < p; i++)
    {
      double x1 = sc.nextDouble();
      double x2 = sc.nextDouble();
      double dis = Math.sqrt(Math.pow(x1,2) + Math.pow(x2,2));
    if(dis <= q)
      result++;
    }
    System.out.println(result);
  }
}


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

int main() {
	int N, A[110], ans[100];
	bool check = true;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = N - i; j >= 0; j--) {
			if (j == 0) {
				check = false;
				break;
			}
			if (A[j] == j) {
				ans[N - i - 1] = j;
				for (int k = j; k < N - i; k++) {
					A[k] = A[k + 1];
				}
				break;
			}
		}
		if (!check) break;
	}
	if (check) {
		for (int i = 0; i < N; i++) {
			cout << ans[i] << endl;
		}
	}
	else cout << -1;
}

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

ll P;

template <typename T>
class SegmentTree {
	using func_t = function<T(T, T)>;
	const int n;
	const T id;
	func_t merge;
	vector<T> data;
	int size(int n) {
		int res;
		for (res = 1; res < n; res <<= 1);
		return res;
	}
	T sub(int l, int r, int node, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) return data[node];
		return merge(sub(l, r, node * 2, lb, (lb + ub) / 2), sub(l, r, node * 2 + 1, (lb + ub) / 2, ub));
	}
public:
	SegmentTree(int n_, T id_, func_t merge_) :
		n(size(n_)), id(id_), merge(merge_), data(size(n_) * 2, id_) {}
	void Update(int p, T val) {
		p += n;
		data[p] = val;
		while (p >>= 1) data[p] = merge(data[p * 2], data[p * 2 + 1]);
	}
	T Find(int i) {
		return data[i + n];
	}
	T Find(int l, int r) {
		return sub(l, r + 1, 1, 0, n);
	}
};

int main()
{
	ll A, B;
	while (cin >> A >> B >> P, A | B | P) {
		vector<string> se(B - A + 1);
		for (ll i = A; i <= B; i++) {
			ll tmp = i;
			while (tmp) {
				se[i - A].push_back('0' + (tmp % 10ll));
				tmp /= 10ll;
			}
			reverse(se[i - A].begin(), se[i - A].end());
		}
		sort(se.begin(), se.end());
		vector<ll> S(B - A + 1);
		for (ll i = 0; i <= B - A; i++) {
			S[i] = stoll(se[i]);
		}
		vector<ll> dp(B - A + 1);
		SegmentTree<ll> st(B - A + 1, 0, [](ll l, ll r) { return (l + r) % P; });
		for (ll i = 0; i <= B - A; i++) {
			dp[i] = (st.Find(0, S[i] - A) + 1) % P;
			st.Update(S[i] - A, dp[i]);
		}
		ll res = 0;
		for (ll i = 0; i <= B - A; i++) {
			res = (res + dp[i]) % P;
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 13488
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>


#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...)
#define showlr(n,l,r)
#endif

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;
/*------------end of definitions------------*/

int N;

signed main(){

    in(N);
    YN(N==3||N==5||N==7);

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use {
    proconio::{fastout, input, marker::*},
    std::cmp::*,
    std::collections::*,
    std::ops::*,
};

fn gcd(a: usize, b: usize) -> usize {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut x = a[0];
    for &a in a.iter() {
        x = gcd(x, a);
        if x == 1 {
            break;
        }
    }

    if x != 1 {
        println!("not coprime");
        return;
    }

    let m = *a.iter().max().unwrap();
    let mut exist = vec![false; m + 1];
    for &a in a.iter() {
        if exist[a] && a != 1 {
            println!("setwise coprime");
            return;
        }
        exist[a] = true;
    }

    let mut yet = vec![true; m + 1];
    for i in 2..=m {
        if !yet[i] {
            continue;
        }
        let mut count = 0;
        for j in 1..=m / i {
            yet[i * j] = false;
            if exist[i * j] {
                count += 1;
                if count == 2 {
                    println!("setwise coprime");
                    return;
                }
            }
        }
    }
    println!("pairwise coprime");
}


Measured memory_bytes: 18344
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int n, m;

int x[5005], y[5005];
vi compressed_x, compressed_y;

int a[5005][5005];

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

    rep(i, n) {
        cin >> x[i] >> y[i];
        compressed_x.PB(x[i]);
        compressed_y.PB(y[i]);
    }

    sort(all(compressed_x));
    sort(all(compressed_y));

    compressed_x.erase(unique(all(compressed_x)), end(compressed_x));
    compressed_y.erase(unique(all(compressed_y)), end(compressed_y));

    rep(i, n) {
        int xidx = lower_bound(all(compressed_x), x[i]) - begin(compressed_x);
        int yidx = lower_bound(all(compressed_y), y[i]) - begin(compressed_y);

        a[yidx][xidx]++;
    }

    for (int i = 0; i < compressed_y.size()+1; ++i) {
        for (int j = 0; j < compressed_x.size()+1; ++j) {
            if (i - 1 >= 0) a[i][j] += a[i - 1][j];
        }
    }

    for (int i = 0; i < compressed_x.size()+1; ++i) {
        for (int j = 0; j < compressed_y.size()+1; ++j) {
            if (i - 1 >= 0) a[j][i] += a[j][i - 1];
        }
    }

    compressed_x.PB(inf);
    compressed_y.PB(inf);

    rep(i, m) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

        x1 = lower_bound(all(compressed_x), x1) - begin(compressed_x);
        x2 = upper_bound(all(compressed_x), x2) - begin(compressed_x) - 1;
        y1 = lower_bound(all(compressed_y), y1) - begin(compressed_y);
        y2 = upper_bound(all(compressed_y), y2) - begin(compressed_y) - 1;

        if (x2 < 0 || y2 < 0) {
            cout << 0 << endl;
            continue;
        }

        int ans = 0;
        ans += a[y2][x2];
        if (y1 - 1 >= 0) ans -= a[y1 - 1][x2];
        if (x1 - 1 >= 0) ans -= a[y2][x1 - 1];
        if (y1 - 1 >= 0 && x1 - 1 >= 0) ans += a[y1 - 1][x1 - 1];
        
        cout << ans << endl;
    }
}

Measured memory_bytes: 101020
#pragma GCC optimize("Ofast", "unroll-loops")

// #define TEST

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double

int main(void){
    string S, T;
    cin >> S >> T;
    vector<char> s_to_t(26, ' ');
    const int sz = S.length();
    for (int i = 0; i < sz; ++i){
        if (s_to_t[S[i] - 'a'] == ' ')
            s_to_t[S[i] - 'a'] = T[i];
        else if (s_to_t[S[i] - 'a'] != T[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    map<char, bool> appered;
    for (int i = 0; i < 26; ++i){
        char from = (char)('a' + i);
        if (s_to_t[i] == ' ') continue;
        if (appered[s_to_t[i]]){
            cout << "No" << endl;
            return 0;
        }
        appered[s_to_t[i]] = true;
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,ans;
string  s;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    cin>>s;
    for(int i=0;i<n-2;i++){
        if(s[i]=='A'){
            if(s[i+1]=='B' && s[i+2]=='C')ans++;
        }
    }
    cout<<ans;
}


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

int main(){
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++){
		char train[60];
		for (int j = 0; j < 60; j++)train[j] = '?';
		int it = 30;

		std::string str;
		std::cin >> str;

		train[it] = str[0];
		for (int j = 1; j < str.size(); j++){
			if (str[j] == '>'){
				it++;
				if (train[it] != str[j + 1])train[it] = str[j + 1];
			}
			else if (str[j] == '<'){
				it--;
				if (train[it] != str[j + 2])train[it] = str[j + 2];
			}
		}

		for (int j = 0; j < 60; j++){
			if (train[j] != '?')std::cout << train[j];
		}
		std::cout << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1196
#include <bits/stdc++.h> 
#define ll long long 
const int N = 5000001; 
using namespace std; 
int n,m;
int solve(int row,int column,vector<vector<char> > &v,vector<vector<int> > &dp)
{
    int count=0;
    if((row>=n)||(column>=m))
    return 0;
    if((row==n-1)&&(column==m-1))
    return 1;
    if(v[row][column]=='#')
    return 0;
    if(dp[row][column]!=-1)
        return dp[row][column];
        
        count=(solve(row+1,column,v,dp)%(int)(1e9+7))+(solve(row,column+1,v,dp)%(int)(1e9+7));
    return dp[row][column]=(count%(int)(1e9+7));
}
int main()
{
    cin>>n>>m;
    vector<vector<char> > v( n , vector<char> (m));
    vector<vector<int> > dp( n , vector<int> (m,-1));
    char x;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>x;
            v[i][j]=x;
        }
    }
    int row=0;int column=0;
    cout<<solve(row,column,v,dp);
}


Measured memory_bytes: 8624
#include <bits/stdc++.h>
using namespace std;
double p[3000];
double dp[3000][3000];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&p[i]);
    }
    dp[0][0] = 1.0;
    for(int i=1;i<=n;i++)
    {
        dp[i][0] = dp[i-1][0] * (1-p[i]);
        for(int j=1;j<=i;j++)
        {
            dp[i][j] = dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
        }
    }
    double ans = 0;
    for(int i=(n+2)/2;i<=n;i++)
    {
        ans += dp[n][i];
    }
    printf("%.10lf\n",ans);

}


Measured memory_bytes: 68864