akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

const int MAX_N = 2e5 + 5;
const int MOD = 1e9 + 7;

long long pow(long long base, int exp)
{
	long long res = 1;
	for (; exp; exp >>= 1)
	{
		if (exp & 1)
			res = res * base % MOD;
		base = base * base % MOD;
	}
	return res;
}

int n, cnt[MAX_N], par[MAX_N];
long long val[MAX_N], fwd[MAX_N], bwd[MAX_N], ans[MAX_N];
std::vector<int> adj[MAX_N];

long long binom(int n, int k)
{
	return fwd[n] * bwd[k] % MOD * bwd[n - k] % MOD;
}

void init(int x, int p)
{
	par[x] = p;
	val[x] = 1;
	for (int y : adj[x])
		if (y != p)
		{
			init(y, x);
			val[x] = val[x] * val[y] % MOD * binom(cnt[x] + cnt[y] + 1, cnt[x]) % MOD;
			cnt[x] += cnt[y] + 1;
		}
}

std::map<int, long long> map[MAX_N];

void solve(int x, int p)
{
	if (x == 1) ans[x] = val[x];
	else ans[x] = val[x] * map[p][x] % MOD * binom(n - 1, cnt[x]) % MOD;
	for (int y : adj[x])
		if (y != p)
		{
			map[x][y] = ans[x] * pow(val[y], MOD - 2) % MOD * pow(binom(n - 1, cnt[y] + 1), MOD - 2) % MOD;
			solve(y, x);
		}
}

int main()
{
	fwd[0] = bwd[0] = 1;
	for (int i = 1; i < MAX_N; ++i)
	{
		fwd[i] = fwd[i - 1] * i % MOD;
		bwd[i] = pow(fwd[i], MOD - 2);
	}
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int u, v; scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	init(1, 0);
	solve(1, 0);
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", ans[i]);
}

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


int main(){
	int N,M;
	cin>>N>>M;
	
	bool flag[N+1]={};
	
	for(int i=0;i<M;i++){
		int a;
		cin>>a;
		flag[a]=true;
	}
	
	vector<int> ans(N+1,0);
	ans[0]=1;
	
	for(int i=1;i<=N;i++){
		if(i==1){
			if(!flag[i])ans[i]=ans[0];
		}
		else{
			if(!flag[i]){
				ans[i]=mod(ans[i]+ans[i-1]+ans[i-2]);
			}
		}
	}
	
	//for(int i=0;i<N;i++)cout<<ans[i]<<endl;
	
	cout<<ans[N]<<endl;
	
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    ll q;
    cin >> q;
    while(q--) {
        ll cac = 0;
        ll j, k;
        cin >> j >> k;
        ll l;
        l = sqrtl(j * k - 1 );
        if ( j > k ) {
            swap(j, k);
        }
        if ( j == k || j + 1 == k ) {
            cout << 2 * j - 2 << endl;
        }
        else if ( j * k <= l * ( l + 1 ) ) {
            cout << 2 * l - 2 << endl;
        }
        else {
            cout << 2 * l - 1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
n=int(input())
A=Counter([int(i) for i in input().split()])
#print(A)
ans=0
for i in A.items():
#    print(i)
    k=i[0]
    l=i[1]
    if k<l:
        ans+=l-k
    elif l<k:
        ans+=l

print(ans)


Measured memory_bytes: 18676
#include<bits/stdc++.h>
using namespace std;
map<int,char>S;
string s;
int Q,i,j,d=1,q,f;
char c;
main(){
	cin>>s>>Q;
    for(auto c:s)S[j++]=c;
	for(;Q--;q-1?cin>>f>>c,S[d+f==2?--i:j++]=c:d=!d)cin>>q;
	while(i<j)cout<<S[d?i++:--j];
}

Measured memory_bytes: 14720
#include<iostream>
#include<algorithm>
#include<cmath>
int main()
{
	long long a = 0, b = 0, c = 0, ans = 1, rate[100] = {},last=0,k=0,ansa=0,ansb=0,ansc=0;
	std::cin >> a>>b>>c>>k;
	bool okada = true;
	if (k == 0) {
		std::cout << a - b<<std::endl;
		okada = false;
	}

	if (okada) {
		if (k % 2 == 1) {
			std::cout << -a + b << std::endl;
	}
		else {
			std::cout << a - b << std::endl;
		}
	}


}







Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#define ll long long
#define INF 0x3f3f3f3f
#define SIS std::ios::sync_with_stdio(false)
using namespace std;

int main()
{
    int num[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int n;
    while(cin>>n)
    {
        cout<<num[n-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

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

    int n, a, b;
    cin >> n >> a >> b;
    vector<int> p(n);
    rep(i, n) cin >> p[i];

    int x, y, z;
    x = y = z = 0;
    rep(i, n){
        if(p[i] <= a){
            x++;
            continue;
        }
        if(p[i] >= b + 1){
            z++;
            continue;
        }
        y++;
    }
    cout << min(x, min(y, z)) << endl;

    return 0;
}


Measured memory_bytes: 888
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
List=[a,b,c,d,e]
for i in range(len(List)):
    for j in range(i+1,len(List)):
        if List[j]-List[i]>k:
            print(":(")
            exit()
print("Yay!")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printv(x) for(int i = 0; i < x.size(); i++){ cout << (x[i]) << " "; } cout << endl; 
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define INF (1e9)
typedef long long ll;
typedef struct{
    int x;
    int y;
} P;

using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,K;
    int A[200010];
    cin >> N >> K;
    rep(i,0,N){
        cin >> A[i];
    }
    int cnt[200010] = {};
    rep(i,0,N){
        cnt[A[i]]++;
    }
    sort(cnt, cnt+N+1, greater<int>());
    ll ans = 0;
    rep(i,0,N+1){
        if(i >= K){
            ans += cnt[i];
        }
    }
    print(ans);
    

}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0 ; i < n ; i++) {
            a[i] = sc.nextInt();
        }
        int[] cnt = new int[1000007];
        for (int x : a) {
            for (int d = 2 ; d * d <= x ; d++) {
                int c = 0;
                while (x % d == 0) {
                    c++;
                    x /= d;
                }
                cnt[d] = Math.max(cnt[d], c);
            }
            if (x > 1 && cnt[x] == 0) {
                cnt[x] = 1;
            }
        }
        long lcm = 1;
        for (int i = 1 ; i < cnt.length ; i++) {
            lcm = lcm * pow(i, cnt[i]) % mod;
        }
        int ans = 0;
        for (int x : a) {
            ans += lcm * pow(x, mod - 2) % mod;
            ans %= mod;
        }
        System.out.println(ans);

    }

    static int pow (long b, int e) {
        long ans = 1;
        while (e > 0) {
            if (e % 2 == 1) {
                ans = ans * b % mod;
            }
            e >>= 1;
            b = b * b % mod;
        }
        return (int) ans;
    }

}

Measured memory_bytes: 38352
from collections import defaultdict

n=int(input())
a=list(input())
b=list(input())
c=list(input())

ans=0
for i in range(n):
    d=defaultdict(int)
    d[a[i]]+=1
    d[b[i]]+=1
    d[c[i]]+=1
    ans+=3-max(d.values())
print(ans)


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a;
    int b;
    int answer =0;
    bool c =false;
    cin >> a >> b;
    int cnt=0;
    
    for(int i=0; i<59; i++){
        cnt = std::pow(b,i);

        if(cnt >a){
            answer = i;
            bool c = true;
             if(c) {break;}
        }
        if(c) {break;}
    }
    
    cout << answer << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
  vector<pair<ll,ll>>a(n);
  for(int i=0;i<n;i++)
  cin>>a[i].first>>a[i].second;
  ll p=0,r=0;
  for(int i=0;i<n;i++)
  {
      if(a[i].first==a[i].second)
      p++;
      else
      {
          if(p>2)
          {
         r=1;
          break;
          }
          p=0;
      }
  }
  if(p>2)
  r=1;
  if(r)
  cout<<"Yes";
  else
  cout<<"No";
}

Measured memory_bytes: 3624
#include<stdio.h>
int main(void){
	int L,M,N,gain;
	int cnt,i;

	for(;;){
	scanf("%d",&L);
	if(L==0){
		return 0;
	}
	gain=0;
	cnt=0;
	for(i=0;i<12;i++){
		scanf("%d %d",&M,&N);
		gain+=(M-N);
		if(L<=gain){
			cnt++;
		}
	}
	if(cnt==0){
		printf("NA\n");
	}
	for(i=0;i<12;i++){
		if(cnt==12-i){
			printf("%d\n",i+1);
		}
	}
		}
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        long min = 1000000000;
        long max = 0;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            if(Math.abs(a[i])>max) max = Math.abs(a[i]);
            if(Math.abs(a[i])<min) min = Math.abs(a[i]);
        }
        sc.close();
        System.out.println(max-min);
    }
}

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

int main(){
  int N;
  vector<int> a;
  cin >> N;
  for(int i = 0; i < N; ++i)
  {
    int n;
    cin >> n;
    a.push_back(n);
  }
  
  sort(a.begin(), a.end(), greater<int>());
  
  int score = 0;
  for(int i = 0; i < N; ++i)
  {
    score += i%2==0 ? a[i] : a[i] * (-1);
  }
  
  cout << score << endl;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
string an;
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    an+='0'+a%10; 
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=505;
int n,a[N],ans[N*N];
PI b[N];
int main(){
	n=read();
	for(int i=1;i<=n;i++){ans[a[i]=read()]=i; b[i]=mp(a[i],i);}
	sort(&b[1],&b[n+1]);
	int dq=1;
	for(int i=1;i<=n;i++){
		int t=b[i].second;
		for(int j=1;j<t;j++){
			while(ans[dq])if(ans[dq++]==t){puts("No"); return 0;}
			ans[dq++]=t;
		}
	}
	dq=n*n;
	for(int i=n;i;i--){
		int t=b[i].second;
		for(int j=t+1;j<=n;j++){
			while(ans[dq])if(ans[dq--]==t){puts("No"); return 0;}
			ans[dq--]=t;
		}
	}
	puts("Yes");
	for(int i=1;i<=n*n;i++){
		write(ans[i]); an+=' ';
	}
	cout<<an;
}

Measured memory_bytes: 3204
#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
    	int x;
    	int y;
    	int result;
    	cin>>x>>y;
    	if(y>=2*x && y<=4*x && y%2==0){
    		cout<<"Yes"<<endl;
    	}else cout<<"No"<<endl;
    	return 0;
    }

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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string>S(N);
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
  }
  sort(S.begin(),S.end());
  for (int i = 0; i < N; i++) {
    cout << S.at(i);
  }
}


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

int main(){
  int n;
  cin>>n;
  long long  A[n];
  long long ans=0;
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  sort(A,A+n);
  ans=A[n-1];
  for(int i=0;i<n-2;i++){
    ans+=A[n-2-i/2];
    //cout<<ans<<endl;
  }
  cout<<ans<<endl;
  return 0;
}

    
  
  

Measured memory_bytes: 5168
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC085A
{
    class Program
    {
        static void Main(string[] args)
        {
            String s;
            s = Console.ReadLine();

            char[] cs = s.ToCharArray();

            cs[3] = '8';

            Console.WriteLine(cs);

            Console.ReadKey();

        }
    }
}

Measured memory_bytes: 11092
import java.util.Scanner

object Main extends App  {
  val sc = new Scanner(System.in)
  val n = sc.nextLong

  val nSqrt = Math.sqrt(n).floor.toLong

  val a = (nSqrt to 1 by -1).find(n % _ == 0).get
  val res = (n / a ).toString.length

  println(res)
}


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

int main() {
int n;
cin>>n;
while(n!=0){
	int ap=0,bp=0;
	int a,b;
	for(int k=0;k<n;k++){
		cin>>a>>b;
		if(a>b){
			ap=ap+a+b;
		}
		else if(a<b){
			bp=bp+a+b;
		}
		else{
			ap=ap+a;
			bp=bp+a;
		}
	}
	cout<<ap<<" "<<bp<<endl;
	cin>>n;
}
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2000001145
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
int ceil2(int a,int b){if(a%b){return a/b+1;}else{return a/b;}}
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};

int ans;
int n,m;
int a[111111];

signed main(){
	
	cin>>n;
	rep(i,n)cin>>a[i];
	multiset<int> s;
	rep(i,n){
		auto itr=s.lower_bound(a[i]);
		if(itr==s.begin())s.insert(a[i]);
		else {
			itr--;
			s.erase(itr);
			s.insert(a[i]);
		}
	}
	cout<<s.size()<<endl;
}


Measured memory_bytes: 5760
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    D = [float('inf')]*N
    for i in range(N):
        num = -I()
        index = bisect_right(D, num)
        D[index] = num

    res = 0
    for i in D:
        if i != float('inf'):
            res+=1
        else:
            break
    print(res)




if __name__ == "__main__":
    main()

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

const int NUM = 1e6;

int main(){
    int n;
    ll sum=0, ans=0;
    
    cin>> n;

    map<ll, ll> a;
    for(int i=0; i<n; i++){
        ll input;
        cin>>input;
        a[input]++;
        sum+=input;
    }
   // cout<<sum<<endl;
    int q;
    cin>>q;
    for(int i=0; i<q; i++){
        ll b, c;
        cin>> b >>c;

        sum-=a[b]*b;
        sum+=a[b]*c;
        if(c!=b){
            a[c]+=a[b];        
            a[b]=0;
        }

        cout<<sum<<endl;
    }
    return 0;
}

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

using namespace std;
using int_vec = vector<int>;

void print(const int_vec& v) {
    int_vec::const_iterator it;
    for (it = v.begin(); it != v.end()-1; ++it) {
        cout << *it << " ";
    }
    cout << *it << endl;
}

void insertion_sort(int_vec& v) {
    for (int i = 1; i < v.size(); ++i) {
        int x = v[i];
        int j;
        for (j = i; j >= 0; --j) {
            if (x >= v[j-1])
                break;
            v[j] = v[j-1];
        }
        v[j] = x;
        print(v);
    }
}

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

    int_vec v;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    print(v);
    insertion_sort(v);

    return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9;
const int MOD=1e9+7;
const int MAXN=1e6+7;

int ans=0;
int n,m,k,q,r;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>r;
    if(n>=10){
        cout<<r<<"\n";
    }else{
        cout<<r+(100*(10-n))<<"\n";
    }
    return 0;
}


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

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

    vector<int> x(N);
    x[0]=accumulate(a.begin(),a.end(),0LL);
    for(int i=1;i<N;i+=2) x[0]-=2*a[i];

    for(int i=0;i<N-1;i++){
        x[i+1]=2*a[i]-x[i];
    }

    for(int i=0;i<N;i++){
        cout<<x[i]<<endl;
    }
    return 0;
}

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

int main()
{
    int n,nAC=0,nWA=0,nTLE=0,nRE=0,i;
    string in;
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>in;
        if(in=="AC")
            nAC++;
        else if(in=="WA")
            nWA++;
        else if(in=="TLE")
            nTLE++;
        else
            nRE++;
    }
    cout<<"AC x "<<nAC<<endl;
    cout<<"WA x "<<nWA<<endl;
    cout<<"TLE x "<<nTLE<<endl;
    cout<<"RE x "<<nRE<<endl;
    return 0;
}

Measured memory_bytes: 3600
import queue
from collections import namedtuple
T = namedtuple("T", "u d")

n = int(input())
path = dict()
ans = [-1] * (n + 1)

for i in range(n):
    a = [int(x) for x in input().split()]
    a.reverse()

    u, k = a.pop(), a.pop()
    path[u] = set()
    for j in range(k):
        path[u].add(a.pop())


def bfs(s):
    q = queue.Queue()
    q.put(s)

    while q.qsize() != 0:
        p = q.get()
        if p.d < ans[p.u] or ans[p.u] < 0:
            ans[p.u] = p.d
            for r in path[p.u]:
                q.put(T(r, p.d + 1))


bfs(T(1, 0))
for i in range(1, n + 1):
    print(i, ans[i])



Measured memory_bytes: 7068
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vs = vector<string>;
using vp = vector<pii>;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (ll)((x).size())
#define all(x) (x).begin(), (x).end()
#define each(a, x) for (auto&& a : (x))
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, n) for (ll i = (a); i < (n); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
#define _per(i, n) peri(i, 0, n)
#define peri(i, a, n) for (ll i = (n) - 1; i >= (a); --i)
#define per(...) _overload3(__VA_ARGS__, peri, _per)(__VA_ARGS__)
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
template<typename T> inline void chmax(T& a, const T& b) {if (a < b) a = b;}
template<typename T> inline void chmin(T& a, const T& b) {if (a > b) a = b;}
template<typename T> inline void print(const T& x) {cout << x << "\n";}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) {is >> p.fi >> p.se; return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) {os << p.fi << " " << p.se; return os;}
template<typename T> istream& operator>>(istream& is, vector<T>& v) {each(in, v) is >> in; return is;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {rep(i, sz(v)) {os << v[i] << (i + 1 != sz(v) ? " " : "");} return os;}
struct Init {Init() {ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(10);}} init;

ll modpow(ll a, ll n) {
    ll val = 1;
    while (n > 0) {
        if (n & 1) val = val * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return val;
}

ll comb(ll n, ll k) {
    ll val = 1;
    rep(i, n - k + 1, n + 1) {
        val *= i;
        val %= MOD;
    }
    rep(i, 1, k + 1) {
        val *= modpow(i, MOD - 2);
        val %= MOD;
    }
    return val;
}

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = MOD + MOD + modpow(2, n) - 1 - comb(n, a) - comb(n, b);
    print(ans % MOD);
}

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

using namespace std;

int dp[3005][3005];
char str[3005];
int main()
{
	string s,t;
	cin>>s>>t;
	for(int i=0;i<=s.length();++i)
	{
		for(int j=0;j<=t.length();++j)
		{
			if(i == 0|| j == 0)
			dp[i][j] = 0;
			else if(s[i-1] == t[j-1])
			dp[i][j] = dp[i-1][j-1]+1;
			else 
			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int i = s.length(), j = t.length(),index = dp[s.length()][t.length()]-1;
	str[index+1] = '\0';
	while(i > 0 && j > 0)
	{
		if(s[i-1] == t[j-1])
		{
			str[index--] = s[i-1];
			i--,j--;
		}
		else 
		{
			if(dp[i-1][j] > dp[i][j-1])
			i--;
			else
			j--;
		}
	}
	printf("%s\n",str);
	return 0;
}


Measured memory_bytes: 35456
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#define pi 3.14159265358979323846264338327950

int main() {
	long long N, K; std::cin >> N >> K;
	std::cout << std::min(N % K, K - N % K) << std::endl;

	return 0;
}

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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    if (B <= C) {
        cout << 0 << endl;
    }
    else if (D <= A) {
        cout << 0 << endl;
    }
    else if (A <= C && B <= D) {
        cout << B - C << endl;
    }
    else if (C <= A && D <= B) {
        cout << D - A << endl;
    }
    else if (A <= C && D <= B) {
        cout << D - C << endl;
    }
    else if (C <= A && B <= D) {
        cout << B - A << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>

using namespace std;
namespace {

	void chmin(long long& x, long long y)
	{
		if (x > y || x < 0)
			x = y;
	}

	void chmax(long long& x, long long y)
	{
		if (x < y)
			x = y;
	}

	long long gcd(long long a, long long b) {
		if (b == 0) return a;
		else return gcd(b, a%b);
	}

	long long gcd(long long a, long long b, long long c) {
		return gcd(gcd(a, b), c);
	}

	void core()
	{
		long K;
		cin >> K;

		long long ret(0);
		for (long a = 1; a <= K; ++a)
			for (long b = 1; b < a; ++b)
				for (long c = 1; c < b; ++c)
					ret += gcd(a, b, c) * 6;

		for (long a = 1; a <= K; ++a)
			for (long b = 1; b < a; ++b)
				ret += gcd(a, b) * 6;

		for (long a = 1; a <= K; ++a)
			ret += a;

		cout << ret;
	}
}

int main()
{
	core();

	return 0;
}

//int main()
//{
//	for (long i = 0; i < 3; ++i)
//	{
//		cout << "Input test" << endl;
//		core();
//		cout << endl;
//	}
//
//	cout << "test ended" << endl;
//
//	int ret;
//	cin >> ret;
//
//	return 0;
//}

Measured memory_bytes: 3572
#include<cstdio>
#include<algorithm>
#define MAXN 106
using namespace std;
int n,a[MAXN],ans=99999999;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int j=-100;j<=100;j++)
	{
		int sum=0;
		for(int i=1;i<=n;i++)
			sum+=(j-a[i])*(j-a[i]);
		ans=min(ans,sum);
	}
	printf("%d",ans);
}

Measured memory_bytes: 760
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
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; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

ll  N,A,B,C,L[10],mi=INF;

void dfs(ll i,ll a,ll b,ll c,ll cost){
    if(i==N){
        if(a==0 || b==0 || c==0){
            return;
        }
        else{
            mi = min(mi,cost+abs(a-A)+abs(b-B)+abs(c-C));
        }
        return;
    }
    dfs(i+1,a+L[i],b,c,cost+(a>0?10:0));
    dfs(i+1,a,b+L[i],c,cost+(b>0?10:0));
    dfs(i+1,a,b,c+L[i],cost+(c>0?10:0));
    dfs(i+1,a,b,c,cost);
}

int main(){
    cin >> N >> A >> B >> C;
    rep(i,N){
        cin >> L[i];
    }
    dfs(0,0,0,0,0);
    cout << mi << endl;
}

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

using namespace std;

int main(){
  long long a,b,c,k;
  cin >> a >> b >> c >> k;
  long long sum=0;
  if(1<=k && k<=a)sum = k*1;
  else if(a <= k && k <= a+b)sum = a*1;
  else if(a+b <= k && k <= a+b+c)sum = a*1 - (k-a-b)*1;

  cout << sum;

return 0;
}

Measured memory_bytes: 3192
#!/usr/bin/env python3
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(l[k-1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
using ll = long long;
using ull = unsigned long long;
ull mod = 1e9 + 7;
using namespace std;

int main(){

  string S; cin >> S;
  vector<ll> a(S.size() + 1, 0);
  for(ll i = 0; i < S.size(); ++i){
    if(S[i] == '<')a[i + 1] = max(a[i + 1], a[i] + 1);
  }

  for(ll i = S.size() - 1; i >= 0; --i){
    if(S[i] == '>')a[i] = max(a[i], a[i + 1] + 1);
  }

  ll ans = 0;
  rep(i, a.size())ans += a[i];

  cout << ans;

}

Measured memory_bytes: 4740
#include <bits/stdc++.h>
using namespace std;
using ivec = vector<int>;

int main() {
	int n, p, q;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	for (cin >> n >> q, p = 1; p*p <= n; ++p);
	ivec c(n);
	for (auto &color: c)
		cin >> color, --color;
	ivec l(q), r(q); priority_queue<tuple<int,int,int>> s;
	for (int m = p-1, i = 0; i < q; ++i)
		cin >> l[i] >> r[i], s.emplace(--r[i]/m,--l[i]/m,i);
	const auto s_dec = [](int &count, int &size) { if (--count == 0) --size; };
	const auto s_inc = [](int &count, int &size) { if (++count == 1) ++size; };
	ivec count(n,0), ans(q); ++count[c[0]];
	for (int g = 0, h = 0, size = 1; not s.empty(); s.pop()) {
		int i = get<2>(s.top()), u = l[i], v = r[i]; 
		while (h > v)
			s_dec(count[c[h--]],size);
		while (h < v)
			s_inc(count[c[++h]],size);
		while (g < u)
			s_dec(count[c[g++]],size);
		while (g > u)
			s_inc(count[c[--g]],size);
		ans[i] = size; }
	for (auto a: ans)
		cout << a << '\n'; }


Measured memory_bytes: 19424
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {

long long int a, b, r, haco1, haco2, maxky, minkb;

while (1) {

	cin >> a >> b;
	haco1 = a;
	haco2 = b;
	
	if ( cin.eof() ){
		break;
	}	

	//loop of maxky
		while(1){
				if(b == 0) {
					maxky = a;
					break;
				}
			r = a % b;
				if(r == 0){
					maxky = b;
					break;
				}
			a = b % r;
				if(a == 0){
					maxky = r;
					break;
				}			
			b = r % a;
		}
		
		//minkb
		
		minkb = (haco1 * haco2) / maxky;

	cout << maxky << " " << minkb << endl; 		
}


    return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define ll long long
#define int long long

using namespace std;

const int maxn = 3010;
const int mod = 1e9+7;

int qsm(int i,int j)
{
	int ans=1;
	while (j)
	{
		if (j&1) ans=ans*i%mod;
		j>>=1;
	    i=i*i%mod;
	}
	return ans;
}

int dp[maxn][maxn];
int n,m;
int q;
int a[maxn];

signed main()
{
   scanf("%lld%lld",&n,&m);
   for (int i=1;i<=n;i++) scanf("%lld",&a[i]);//a[i]=read();
   for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
       dp[i][j]=(a[i]>a[j]);// a[i]在前，a[j]在后形成逆序对的概率 
   int inv = qsm(2,mod-2);
   for (int i=1;i<=m;i++)
   {
   	  int x,y;
   	  scanf("%lld%lld",&x,&y);
   	  dp[x][y]=dp[y][x]=(dp[x][y]+dp[y][x])*inv%mod;
   	  for (int i=1;i<=n;i++)
   	  {
   	  	if (i!=x && i!=y)
   	  	{
   	  		dp[x][i]=dp[y][i]=(dp[x][i]+dp[y][i])*inv%mod;
   	  		dp[i][x]=dp[i][y]=(dp[i][x]+dp[i][y])*inv%mod;
		}
	  }
   }
   int ans=0;
   for (int i=1;i<=n;i++)
     for (int j=i+1;j<=n;j++)
        ans=(ans+dp[i][j])%mod;
   cout<<ans*qsm(2,m)%mod;
   return 0;
}

Measured memory_bytes: 70784
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int H, W;

		while (true) {
			H = scanner.nextInt();
			W = scanner.nextInt();

			if (H == 0 && W == 0)
				break;

			for (int i = 0; i < H; i++) {
				if (i == 0 || i == H - 1) {
					for (int i2 = 0; i2 < W; i2++) {
						System.out.print("#");
					}
				} else {
					for (int i2 = 0; i2 < W; i2++) {
						if (i2 == 0 || i2 == W - 1) {
							System.out.print("#");
						} else {
							System.out.print(".");
						}
					}
				}

				System.out.println();
			}

			System.out.println();
		}
	}
}

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

public class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] stringArray = br.readLine().split("");

        int count=0;

        for(int i=0; i<3; i++){
            if(stringArray[i].equals("7")){
                count++;
            }
        }
        if(count != 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

    }


}

Measured memory_bytes: 32752
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

class Main {
	public static void main(String args[]) throws IOException {
		@SuppressWarnings("resource")
		Scanner cin = new Scanner(System.in);
		ArrayList<String> inLines = new ArrayList<String>();
		for (; cin.hasNext();) {
			inLines.add(cin.nextLine());
		}
		Solver solver = new Solver();
		solver.solve(inLines);
	}
}

class Solver {

	public void solve(ArrayList<String> inLines) {
		int x = Integer.parseInt(inLines.get(0));
		if (x < 1200)
			System.out.println("ABC");
		else
			System.out.println("ARC");
	}
}


Measured memory_bytes: 9672
import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner x=new Scanner(System.in);
        int a=x.nextInt();
        int ans=0;
        while(111<=a&&a<=999){
            int b=a/100;
            int c=a%100/10;
            int d=a%100%10/1;
            ans=(10-b)*100+(10-c)*10+(10-d);
            break;
        }
        System.out.println(ans);
     }
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int n,m,q;  cin >> n >> m >> q;
  vector<int> v[501];
  for(int i = 0; i < m; ++i){
    int l,r; cin >> l >> r;
    v[r].push_back(l);
  }
  vector<P<int,int>> qry[501];
  for(int i = 0; i < q; ++i){
    int l,r; cin >> l >> r;
    qry[r].emplace_back(l,i);
  }
  vector<int> ans(q);
  vector<int> fnd;
  fnd.reserve(m);
  for(int i = 0; i <= n; ++i){
    for(auto e:v[i])
      fnd.insert(upper_bound(fnd.begin(),fnd.end(),e),e);
    for(auto e:qry[i]){
      ans[e.second] = distance(lower_bound(fnd.begin(),fnd.end(),e.first),fnd.end());
    }
  }
  for(auto e:ans)cout << e << endl;
}


Measured memory_bytes: 6844
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def f(a, b, x):
    return (a*x)//b - a*(x//b)
def main():
    a, b, n = map(int, readline().split())
    if n < b:
       ans = f(a, b, n) 
    else:
        ans = f(a, b, b-1)
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 9252
# cf17-finalA - AKIBA
def main():
    S = input().rstrip()
    SR = S.replace("A", "")
    flg = SR == "KIHBR" and "AA" not in S and "KIH" in S
    print("YES" if flg else "NO")


if __name__ == "__main__":
    main()

Measured memory_bytes: 2940
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
//V,P(大文字)使用不可
//乗算の際にオーバーフローに注意せよ！！（適切にmodをとれ）

const ll INF=1e18;

signed main(){
    int n,m;
    cin>>n>>m;
    if(m>0){
         V<int> s(m),c(m);
    rep(i,m) cin>>s[i]>>c[i];
        V<set<int>> st(n);
    rep(i,m) st[s[i]-1].insert(c[i]);
    bool ok=1;
    rep(i,n){
        if(st[i].size()>1) ok=0;
    }
    string t;
    if(ok){
        if(n==1){
            if(st[0].size()==0) t="0";
            else t=to_string(*begin(st[0]));
        }else{
            rep(i,n){
            if(i==0&&!st[i].empty()&&*begin(st[i])==0) ok=0;
            else if(i==0){
                if(st[i].size()==0) t+='1';
                else t+=to_string(*begin(st[i]));
            }
            else{
                if(st[i].size()==0) t+='0';
                else t+=to_string(*begin(st[i]));
            }
        }
    }
        }
        
    if(ok) cout<<t<<endl;
    else cout<<-1<<endl;
    }else{
        string t;
        if(n==1) t="0";
        else{
            t+='1';
        rep(i,n-1) t+='0';
        }
        cout<<t<<endl;
    }
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

template<int n>
struct BG {
    vector<int> adj[n];
    bool vis[n];
    int match[n];

    void clear() {
        for (int u = 0; u < n; ++u) {
            adj[u].clear();
        }
    }

    void add_edge(int x, int y) {
        adj[x].push_back(y);
    }

    bool dfs(int x) {
        for (auto y : adj[x]) {
            if (vis[y]) continue;
            vis[y] = true;
            if (!~match[y] || dfs(match[y])) {
                match[y] = x;
                return true;
            }
        }
        return false;
    }

    int max_match() {
        int cnt = 0;
        for (int u = 0; u < n; ++u) match[u] = -1;
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) vis[v] = false;
            cnt += dfs(u);
        }
        return cnt;
    }
};

const int maxn = 100;

int n, m;
BG<maxn> bg;
int a[maxn][maxn];

void print() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << a[i][j] + 1 << " ";
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);

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

    for (int k = 0; k < m; ++k) {
        bg.clear();
        for (int i = 0; i < n; ++i) {
            for (int j = k; j < m; ++j) {
                bg.add_edge(a[i][j] / m, i);
            }
        }
        assert(bg.max_match() == n);
        for (int i = 0; i < n; ++i) {
            for (int j = k; j < m; ++j) {
                if (bg.match[i] == a[i][j] / m) {
                    swap(a[i][k], a[i][j]);
                }
            }
        }
    }

    print();

    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            for (int k = i; k < n; ++k) {
                if (a[k][j] / m == i) {
                    swap(a[k][j], a[i][j]);
                    break;
                }
            }
        }
    }

    print();

    return 0;
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

#define min(a, b) ((a) < (b)? (a):(b))
#define max(a, b) ((a) > (b)? (a):(b))
#define rep(i, n) REP(i, 0, (n))
#define REP(i, a, n) for(typeof(n) i=(a); i<(n); i++)

int main() {
	int N; cin >> N;
	string s; cin >> s;
    int x = 0, maxx = 0;
    rep(i, s.size()) {
        if(s[i]=='I') x++;
        else x--;
        maxx = max(maxx, x);
    }
    cout << maxx << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

typedef vector<ll> vec;
typedef vector<vec> mat;
typedef long long ll;

const ll M = 1E9 + 7;


mat mul(mat &A,mat &B) {
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0;i < A.size();i++) {
        for (int k = 0;k < B.size();k++) {
            for (int j = 0;j < B[0].size();j++) {
                C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % M) % M;
            }
        }
    }
    return C;
}

mat pow(mat A, ll n) {
    mat B(A.size(), vec(A.size()));
    for (int i = 0;i < A.size(); i++) {
        B[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2) B = mul(B,A);
        A = mul(A,A);
        n /= 2;
    }
    return B;
}

ll power(ll a, ll b) {
	ll res = 1;
	while (b > 0) {
		if (b % 2) {
			res *= a;
			res %= M;
		}
		a *= a;
		a %= M;
		b /= 2;
	}
	return res;
}

char X[1010][1010];

int main() {
    ios::sync_with_stdio(false);
    int H, W;
    ll K;
    cin >> H >> W >> K;
    for (int i = 0;i < H;i++) {
    	for (int j = 0;j < W;j++) cin >> X[i][j];
    }
    if (K == 0) {
        cout << 0 << endl;
        return 0;
    }
    ll h = 0, v = 0, x = 0, y = 0, t = 0;
    for (int i = 0;i < H;i++) {
    	for (int j = 0;j < W;j++) {
    		if (X[i][j] == '.') continue;
    		t++;
    		if (X[(i + 1) % H][j] == '#') {
    			if (i == H - 1) x++;
    			else v++;
    		}
    		if (X[i][(j + 1) % W] == '#') {
    			if (j == W - 1) y++;
    			else h++;
    		}
    	}
    }
    if (x == 0 && y == 0) {
    	cout << power(t, K - 1) << endl;
    	return 0;
    }
    if (x > 0 && y > 0) {
    	cout << 1 << endl;
    	return 0;
    }
    mat C(2, vec(2));
    if (x != 0) {
    	C[0][0] = t;
    	C[0][1] = M - v;
    	C[1][0] = 0;
    	C[1][1] = x;
    }
    else {
    	C[0][0] = t;
    	C[0][1] = M - h;
    	C[1][0] = 0;
    	C[1][1] = y;
    }
    mat D = pow(C, K - 1);
    cout << (D[0][0] + D[0][1]) % M << endl;
    return 0;
}


Measured memory_bytes: 1280
N = int(input())
S = input()

tmp_ans = S[1:].count("E")
ans = tmp_ans
# print(tmp_ans)
for i in range(1, N):
    if S[i-1] == "W":
        tmp_ans += 1
    if S[i] == "E":
        tmp_ans -= 1
    # print(tmp_ans)
    if tmp_ans < ans:
        ans = tmp_ans
print(ans)

Measured memory_bytes: 3700
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repl(i,n) for(int64_t i=0;i<(int64_t)(n);i++)
#define MAX_N 10000000
#define ll int64_t
#define all(v) (v).begin(),(v).end()
#define P pair<int,int>
using namespace std;

int main() {
  ll n,count=0,ren=0; cin>>n;
  vector<string> s(n);
  rep(i,n) {
    cin>>s[i];
    sort(all(s[i]));
    }
    sort(all(s));
    rep(i,n-1) {
      if(s[i]==s[i+1]) {
        count++; count+=ren;
        ren++;
      }
      else ren=0;
    }
    cout<<count<<endl;
    return 0;
}

Measured memory_bytes: 7296
hoge = input().split()

N = int(hoge[0])
K = int(hoge[1])

p_list = list(map(int,input().split()))
  
big = 0
s = [0] * (N+1)
for i in range(N):
  s[i+1] = s[i] + p_list[i]

res = 0
for i in range(N-K+1):
  val = s[K+i] - s[i]
  if res < val:
    res = val

ans = (float(res) / 2) + 0.5 * float(K) 
print(ans)

Measured memory_bytes: 24804
#include <iostream>
#include <numeric>

void solve() {
    int x;
    std::cin >> x;
    std::cout << 360 / std::gcd(x, 360) << "\n";
}

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

    solve();

    return 0;
}


Measured memory_bytes: 3668
import copy

def j(n):
    if n:print("Yes")
    else:print("No")
    exit(0)
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
s =0
m,d = ips()
for i in range(1,m+1):
    for k in range(1,d+1):
        if k >= 20 and (k%10) >= 2:
            if (k%10) * (k//10) == i:
                s+=1
print(s)


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

using namespace std;
using LL = long long;

int main(){
	LL N, K;
	cin >> N >> K;
	vector<LL> A(N), B(N+1), sum(N+1);
	rep(i,N) cin >> A[i];
	rep(i,N) sum[i+1]=sum[i]+A[i];
	rep(i,N) sum[i+1]%=K;
	rep(i,N) B[i+1]=sum[i+1]-(i+1);
	map<LL,vector<int>> m;
	rep(i,N+1){
		B[i]%=K;
		if(B[i]<0) B[i]+=K;
	}
	rep(i,N+1) m[B[i]].emplace_back(i);
	LL ans=0;
	rep(i,N+1){
		LL b=B[i];
		int j=lower_bound(m[b].begin(),m[b].end(),i)-m[b].begin();
		int k=upper_bound(m[b].begin(),m[b].end(),i-K)-m[b].begin();
		ans+=j-k;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 26752
def main():
    N = int(input())
    W = list(map(int, input().split()))
    total = sum(W)
    cumsum = 0
    ans = total
    for i in range(N):
        cumsum += W[i]
        ans = min(ans, abs(total - cumsum*2))
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 38480
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int N, ans = 0, x = 0; string S; cin >> N >> S;
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'I') x++;
        else x--;
        ans = max(ans, x);
    }
    printf("%d\n", ans);
}


Measured memory_bytes: 3680
import sys, os

if __name__=='__main__':
    if 'local' in os.environ :
        sys.stdin = open("./input.txt", "r")

    a,b,c,d,e,k = int(input()),int(input()),int(input()),int(input()),int(input()), int(input())

    if e-a>k:
        print(":(")
    else:
        print("Yay!")

Measured memory_bytes: 3060
#include<stdio.h>
int main()
{
    int A,B,c,d,e;
    scanf("%d %d",&A,&B);
    c=A+B;
    d=A-B;
    e=A*B;

    if(c>=d && c>=e)
    {
        printf("%d",c);
    }

     else if(d>=c && d>=e)
    {
        printf("%d",d);
    }

     else if(e>=d && e>=c)
    {
        printf("%d",e);
    }

    else if(A==0 && B==0)
    {
        printf("%d",A);
    }

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    string a,b,c;
    cin>>a>>b>>c;
    char c1;
    string str="";
    c1=a.at(0)-('a'-'A');
    str+=c1;
    c1=b.at(0)-('a'-'A');
    str+=c1;
    c1=c.at(0)-('a'-'A');
    str+=c1;
    cout<<str<<endl;
}


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

using namespace std;
using ll = long long int;
#define long ll

template <typename T>
struct SegmentTree {
    using F = function<T(T, T)>;

    const T e;
    const F f;
    size_t sz;
    vector<T> tree;

    SegmentTree(size_t n, const F &f, const T &e = 0) : f(f), e(e) {
        sz = 1;
        while(sz < n) sz <<= 1;
        tree.assign(2*sz, e);
    }

    void set(typename vector<T>::iterator begin, typename vector<T>::iterator end) {
        copy(begin, end, tree.begin() + sz);
        for(size_t k=sz-1; k>0; k--)
            tree[k] = f(tree[2*k+0], tree[2*k+1]);
    }

    void update(size_t k, const T &x) {
        k += sz;
        tree[k] = x;
        while(k >>= 1)
            tree[k] = f(tree[2*k+0], tree[2*k+1]);
    }

    T query(size_t a, size_t b) const {
        T l = e, r = e;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
            if(a & 1) l = f(l, tree[a++]);
            if(b & 1) r = f(tree[--b], r);
        }
        return f(l, r);
    }

    T operator[](const size_t k) const {
        return tree[sz + k];
    }
};

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

    ll n;
    cin >> n;

    using P = tuple<ll,ll,ll>;
    vector<P> v(2*n);
    for(ll i=0; i<n; i++) {
        ll x, y;
        cin >> x >> y;
        v[i] = P(x, 1, y);
    }
    for(ll i=0; i<n; i++) {
        ll x, y;
        cin >> x >> y;
        v[i+n] = P(x, 0, y);
    }

    sort(v.begin(), v.end());

    SegmentTree<long> st(2*n, [&](long a, long b){return max(a, b);}, 0);
    ll r = 0;
    for(auto &t: v) {
        ll x, y, z;
        tie(x, z, y) = t;
        if(z == 1) {
            // red
            st.update(y, st[y]+1);
        } else {
            // blue
            if(!st.query(0, y)) continue;
            ll ok = 0, ng = y;
            while(abs(ok - ng) > 1) {
                ll m = (ok + ng) / 2;
                (st.query(m, y) ? ok : ng) = m;
            }
            st.update(ok, st[ok]-1);
            r++;
        }
    }
    cout << r << endl;
}


Measured memory_bytes: 256