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

using namespace std;
typedef long long int LL;
const int Max_N(100050);

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Weight[Max_N << 1], Size[Max_N], SonMax[Max_N], root;
LL Ans;

inline void Add_Edge(int s, int t, int w)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Weight[Total] = w, Head[s] = Total;
}

void dfsSize(int u, int fa)
{
	Size[u] = 1, SonMax[u] = 0;
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			dfsSize(v, u), Size[u] += Size[v], SonMax[u] = max(SonMax[u], Size[v]);
	SonMax[u] = max(SonMax[u], N - Size[u]);
}

void dfsDist(int u, int fa, LL Dis)
{
	Ans += Dis * 2LL;
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
			dfsDist(v, u, Dis + Weight[i]);
}

/*
考虑提出重心root，可以证明：存在一个最优解，使得哈密顿路上相邻两个点的路径均经过重心
可以先构造出哈密顿回路：把在不同子树中的点两两匹配起来（可能存在孤立点），以root为起点，再考虑root走到的点和走到root的点，显然哈密顿回路 = Sum{2 * Dist(root, i)   |   1 <= i <= N}
然后考虑去掉哈密顿回路上边权最小的边就可以得到答案，显然一定是去掉和root相邻的一个点x到root的路径（是root走到的点或走到root的点）
当最大子树匹配过程中有孤立点时，x必须在可能存在孤立点的子树中
*/

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v, w;i != N;++i)
		scanf("%d%d%d", &u, &v, &w), Add_Edge(u, v, w), Add_Edge(v, u, w);
	dfsSize(1, -1), root = 1;
	for (int i = 2;i <= N;++i)
		if (SonMax[i] < SonMax[root])
			root = i;
	dfsDist(root, -1, 0LL);
	dfsSize(root, -1);
	int Min(0X3F3F3F3F);
	if ((N & 1) && N - 1 >= 2 * SonMax[root])//可以两两匹配，不存在孤立点
		for (int i = Head[root];i;i = Next[i])
			Min = min(Min, Weight[i]);
	else//找可能存在孤立点的子树 
		for (int i = Head[root], v;i;i = Next[i])
			if (Size[v = To[i]] == SonMax[root] || (((N - 2) & 1) == 0 && N - 2 >= 2 * SonMax[root]))
				Min = min(Min, Weight[i]);
	printf("%lld", Ans - Min);
	return 0;
}

Measured memory_bytes: 7680
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <ctype.h>
#include <vector>
using namespace std;

#define ll long long int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define vi vector<int>

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

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

    int ans = 0;
    rep(i, 0, 4)
    {
        if (s[i] == '+')
            ans++;
        else
            ans--;
    }
    cout << ans << endl;
}


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


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unsigned long long int ull;
const ll MOD=1e9+7;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=1e18;

struct UnionFindTree{
    vector<int> par,rank;
    UnionFindTree(int n):par(n),rank(n,0){
        for(int i=0;i<n;i++) par[i]=i;
    }
    int root(int x){
        if(par[x]==x) return x;
        return par[x]=root(par[x]);
    }
    void unite(int x,int y){
        int rx=root(x),ry=root(y);
        if(rx==ry) return ;
        if(rank[rx]<rank[ry]) par[rx]=ry;
        else par[ry]=rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
};

int main(){
    int n,m;cin>>n>>m;
    vector<int> p(n);
    for(int i=0;i<n;i++){
        cin>>p[i];p[i]--;
    }
    UnionFindTree UFT(n);
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        x--;y--;
        UFT.unite(x,y);
    }
    int ans=0;
    for(int i=0;i<n;i++)if(UFT.same(i,p[i])) ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4580
c1, c2, c3 = map(int, input().split())
c4, c5, c6 = map(int, input().split())
c7, c8, c9 = map(int, input().split())

if c1+c5+c9 == c1+c8+c6 == c4+c2+c9 == c4+c8+c3 == c7+c2+c6 == c7+c5+c3:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
int A[200];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N) cin >> A[i];
  vector<int> seq;
  rep(t, N) {
    int pos = -1;
    rep(x, N) if (A[x] == N-1-t) pos = x;
    if (pos == N-1-t) continue;
    // [pos+1, N-1-t]
    for (int i=1; i<=N; i++) {
      seq.pb(1);
      if (pos+1 <= i && i <= N-1-t) swap(A[i-1], A[i]), seq.pb(N-1);
    }
    //rep(i, N) cout<<A[i]<<",";cout<<"\n";
  }
  assert(is_sorted(A, A+N));
  cout << seq.size() << "\n";
  for (int x : seq) cout << x << "\n";
  return 0;
}


Measured memory_bytes: 764
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, K = LI()
    if K > (N - 1) * (N - 2) // 2:
        print(-1)
        return
    M = (N * (N - 1) // 2) - K
    edges = [[N, i] for i in range(1, N)]
    cnt = (N - 1) * (N - 2) // 2
    for i in range(1, N):
        if cnt == K:
            break
        for j in range(i + 1, N):
            edges.append([i, j])
            cnt -= 1
            if cnt == K:
                break
    print(M)
    for e in edges:
        print(*e)
    return

main()

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

int main(){
    ll n;
    long double  d;
    cin>>n>>d;

    int ans=0;
    rep(i,n){
        long double x,y;
        cin>>x>>y;
        long double dis = sqrt(x*x+y*y);
        if(dis<=d){
            ans++;
        }
    }

    cout<<ans<<endl;

}


Measured memory_bytes: 3740
N,X,Y=map(int,input().split())

k=[0]*(N-1)
for i in range(N):
  for j in range(i+1,N):
    k[min(j-i,abs(j+1-Y)+1+abs(i+1-X))-1]+=1
    
for i in range(N-1):
  print(k[i])

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

using namespace std;
using ll = long long;
using P = pair<int, int>;


int main() {
	int d, t, s;
	cin >> d >> t >> s;
	if (t * s >= d) {
		cout<<"Yes"<<endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



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


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

#define MAX 16777216

int Hash[MAX];
char str[13];

int getChar(char);
int getKey();
int find();
void insert();

int main(){
  int n;
  char com[7];

  scanf("%d" ,&n);
  while(n--){
    scanf("%s %s" ,com ,str);

    if(com[0] == 'i'){
      insert();
    }else{
      if(find()){
	puts("yes");
      }else{
	puts("no");
      }
    }
  }

  return 0;
}

int getChar(char ch){
  if(ch == 'A'){
    return 1;
  }else if(ch == 'C'){
    return 2;
  }else if(ch == 'G'){
    return 3;
  }
  return 4;
}

int getKey(){
  int sum = 0, p = 1, i;

  for(i = 0 ; i < strlen(str) ; i++){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int find(){
  int key = getKey();

  if(Hash[key]){
    return 1;
  }

  return 0;
}

void insert(){
  Hash[getKey()] = 1;
}

Measured memory_bytes: 38624
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <queue>
using namespace std;
#define N 300050
#define M 2400050
int head[N],to[M],nxt[M],n,m,cnt,val[M],tot,vis[N],dis[N],S,T;
priority_queue<pair<int,int> >q;
struct A {
	int x,y,z,id;
	bool operator < (const A &u) const {return z<u.z;}
}e[N];
vector<A>G[N];
inline void add(int u,int v,int w) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
int main() {
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=m;i++) {
		scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); e[i].id=i;
		G[e[i].x].push_back(e[i]);
		G[e[i].y].push_back(e[i]);
	}
	tot=m; S=n+m+1,T=n+m+2;
	for(i=1;i<=n;i++) {
		sort(G[i].begin(),G[i].end());
		int lim=G[i].size();
		tot++;
		for(j=0;j<lim;j++) {
			add(G[i][j].id,tot,0);
			add(tot,G[i][j].id,1);
		}
		int k=0,l;
		for(j=0;j<lim;j=k) {
			for(;k<lim&&G[i][j].z==G[i][k].z;k++) ;
			for(l=j+1;l<k;l++) {
				add(G[i][l].id,G[i][l-1].id,0);
				add(G[i][l-1].id,G[i][l].id,0);
			}
		}
		for(j=0;j<lim;j++) {
			if(i==1) add(S,G[i][j].id,0);
			if(i==n) add(G[i][j].id,T,0);
		}
	}
	tot+=2;
	memset(dis,0x3f,sizeof(dis));
	dis[S]=0;
	q.push(make_pair(0,S));
	while(!q.empty()) {
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i]) {
			dis[to[i]]=dis[x]+val[i];
			q.push(make_pair(-dis[to[i]],to[i]));
		}
	}
	if(dis[T]>max(n,m)) puts("-1");
	else printf("%d\n",dis[T]+1);
}













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

int main() {
  int A,B;
  int flag1 = 0;
  int flag2 = 0;
  cin >> A >> B;
  string s;
  cin>>s;
  if(s[A]!= '-'){
   cout << "No" <<endl;
  }else{
    for(int i=0;i<A;i++){
      if('0'>s[i] || s[i]>'9'){
           flag1 = 1;
     
      }
    }
    
    for(int i=A+1;i<A+B+1;i++){
       if('0'>s[i] || s[i]>'9'){
          
         flag2 = 1;
      }
    } 
   if(flag1 == 1 || flag2 == 1){
    cout << "No" << endl;
  }else{
    cout<< "Yes" << endl; 
}
  flag1=0;
  flag2=0;  
    
    
  }
  
 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
    string S;
    cin >> S;
    int N = S.size();
    char c = S[0];
    int count = 0;
    for (int i=0; i < N; i++) {
        if (c != S[i]) {
            count += 1;
            c = S[i];
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI 3.1415926535897
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


signed main(){
	int D;
	cin >> D;

	if(D == 25) cout << "Christmas" << endl;
	else if(D == 24) cout << "Christmas Eve" << endl;
	else if(D == 23) cout << "Christmas Eve Eve" << endl;
	else cout << "Christmas Eve Eve Eve" << endl;

	return 0;

}

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

typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100005;

int main(){
    
    string S;cin>>S;
    string A,B;
    for(int i=0;i<S.size();i++){
        if(S[i]!='x') A+=S[i];
        if(S[S.size()-1-i]!='x') B+=S[S.size()-1-i];
    }
    if(A!=B) cout<<-1<<endl;
    else{
        int N=(A.size()+1)/2;
        vector<int> C(N),D(N);
        int i=0,cnt=0,now=0;
        while(now<N){
            if(S[i]!='x'){
                C[now]=cnt;
                cnt=0;
                now++;
            }else cnt++;
            i++;
        }
        i=S.size()-1;
        now=0;
        while(now<N){
            if(S[i]!='x'){
                D[now]=cnt;
                cnt=0;
                now++;
            }else cnt++;
            i--;
        }
        int ans=0;
        for(int i=0;i<N;i++){
            ans+=abs(C[i]-D[i]);
        }
        
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 1152
//shara's here
#include <bits/stdc++.h>
using namespace std;
typedef int q;
typedef double w;
typedef string s;
typedef long long ll;
int main(){
	q x,ans=0,maxi;
	cin>>x;
	q a[x];
	for(q i=0;i<x;i++){
		cin>>a[i];
	}
	maxi=a[0];
	for(q i=0;i<x;i++){
		if(a[i]>=maxi){
			ans++;
			maxi=a[i];
		}
	}
	cout<<ans<<endl;



















return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


Measured memory_bytes: 256
def draw(h, w):
    for i in range(h):
        s = ""
        for j in range(w):
            s += ("#" if (i + j) % 2 == 0 else ".")
        print(s)
    print("")
  
while True:
    h, w = map(int, raw_input().split())
    if h == 0 and w == 0:
        break
    draw(h, w)

Measured memory_bytes: 6388
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int):
    x = N*800
    y = (N//15) * 200
    print(x-y)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import java.io.*;
import java.util.*;

public class Main{


	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		char c=sc.next().charAt(0);
		out.println(c=='A'?'T':c=='T'?'A':(c=='G'?'C':'G'));
	
		out.close();

	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
 
 
int main() {
	int N, A, B;
 
	cin >> N >> A >> B;
 
	if(N*A > B) cout << B;
	else        cout << N*A;
 
 
}

Measured memory_bytes: 384
N = int(input())
H = list(map(int,input().split()))

def solve(N, H):
	
	dp = [0 for i in range(N)]
	dp[1] = abs(H[0] - H[1])
	
	for i in range(2, N):
		dp[i] = min(dp[i-1] + abs(H[i-1]-H[i]), dp[i-2] + abs(H[i-2]-H[i]));
		
	return dp[N-1]

print(solve(N, H))


Measured memory_bytes: 52720
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define meow(args...) fprintf(stderr, args)
unsigned c[305][305], f[305][305], g[305][305];
int main()
{
	int n, k;
	unsigned m;
	register int i, j, l;
	scanf("%d%d%u", &n, &k, &m);
	for(i=0; i<=k; ++i) f[0][i]=1;
	for(i=0; i<=k; ++i) g[0][i]=i+1;
	for(i=0; i<=n; ++i) {
		c[i][0]=c[i][i]=1;
		for(j=1; j<i; ++j) c[i][j]=(c[i-1][j-1]+c[i-1][j])%m;
	}
	for(i=1; i<=n; ++i) {
		for(j=1; j<=k; ++j) {
			f[i][j]=0;
			for(l=0; l<i; ++l) f[i][j]=(f[i][j]+(unsigned long long)f[l][j]*g[i-l-1][j-1]%m*c[i-1][l])%m;
			g[i][j]=(f[i][j]+g[i][j-1])%m;
		}
	}
	printf("%d\n", f[n][k]);
	return 0;
}


Measured memory_bytes: 1280
#define _GLIBCXX_DEBUG    //空コンテナ操作禁止　Clang環境では#define _LIBCPP_DEBUG 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for( int i=0; i<N; i++ ) cin >> P.at(i);
  
  int cnt = 0;
  for( int i=0; i<N; i++ ){
    if( P.at(i) != i+1 ) cnt++;
  }
  
  if( cnt == 2 || cnt == 0 ){
    cout << "YES";
  }else{
    cout << "NO";
  }  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    static Scanner stdIn = new Scanner(System.in);
    public static void main(String[] args){
        int n = stdIn.nextInt();
        int d = stdIn.nextInt();

        System.out.println((int)Math.ceil((double)n / (2 * d + 1)));
    }
}

Measured memory_bytes: 35616
#include<cstdio>
const int N=2e5+3,INF=1e9;
int n,a[N],b[N],f[N];
inline bool Check(int g){
	int tmp=0,l=n+n,r=0;
	for(int i=1;i<n+n;i++)b[i]=a[i]>g;
	for(int i=2;i<n+n;i++)tmp+=b[i]^b[i-1];
	if(tmp==n+n-2)return!b[1];
	if(b[n]==b[n+1]||b[n]==b[n-1])return!b[n];
	for(int i=n;i>1;i--)
	  if(b[i]==b[i-1]){l=i;break;}
	for(int i=n;i+1<n+n;i++)
	  if(b[i]==b[i+1]){r=i;break;}
	if(l==n+n)return!b[r];
	if(!r)return!b[l];
	return!b[n-l>r-n?r:l];
}
int main(){
	int l,r,m;
	scanf("%d",&n);
	for(int i=1;i<n+n;i++)scanf("%d",a+i);
	for(l=-INF,r=INF;l<r;)m=l+r>>1,Check(m)?r=m:l=m+1;
	printf("%d",l);
	return 0;
}

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

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    char c[101010];
    scanf("%s", c);
    
    // 2. 出力.
    int a = 0, b = 0;
    rep(i, N){
        // 国内.
        if(c[i] == 'a'){
            if(a + b < A + B) puts("Yes"), a++;
            else              puts("No");
        }
        // 海外.
        if(c[i] == 'b'){
            if(a + b < A + B && b < B) puts("Yes"), b++;
            else                       puts("No");
        }
        // どちらでもない.
        if(c[i] == 'c') puts("No");
    }
    return 0;
    
}

Measured memory_bytes: 768
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] book = new String[n];
		for(int i = 1; i <= n; i++) {
			String s = sc.next();
			int temp = sc.nextInt();
			
			s = s + " " + 1/(double)temp  + " "  + i;
			book[i-1] = s;
		}
		Arrays.sort(book);
		for(String ans:book) {
			System.out.println(ans.split(" ")[2]);
		}
	}
}

Measured memory_bytes: 21716
/*input
6
30 10 60 10 60 50
*/

#include <bits/stdc++.h>
#define pb(x) push_back(x);
#define in(y) insert(y);
#define tt(t) while(t--)
#define int long long int
#define itr ::iterator it;
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define si set<int>                      
#define msi map<string, int>
#define lines printsf("\n")
#define ff(n) for(int i=0;i<n;i++)
#define fors(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(),v.end()
#define mp make_pair
using namespace std;
const int MOD = 998244353;
int n;
vi arr;
int dp[1000000];
int solve(int pos){
	if(pos==n-1) return 0;
	if(pos>=n) return 9999999999LL;
	if(dp[pos]!=-1) return dp[pos]; 
	int ret = min(solve(pos+1)+abs(arr[pos]-arr[pos+1]),solve(pos+2)+abs(arr[pos]-arr[pos+2]));
	return dp[pos]=ret;
}
signed main(){
	ff(1000000-1) dp[i]=-1;
	cin>>n;
	arr.resize(n);
	ff(n) cin>>arr[i];
	int ans = solve(0);
	cout<<ans;
}



Measured memory_bytes: 10368
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
bool dp[110000]; //残り　太郎が勝つ
int main() {
 int n,k;
  cin>>n>>k;
  vin a(n);
  rep(i,0,n) cin>>a[i];
  
  rep(i,1,k+1){//残りI個
    rep(j,0,n){
      if(i-a[j]>=0)
     dp[i]|=(!dp[ i-a[j]]);
     
    }
  }
  if(dp[k])cout<<"First"<<endl;
  else cout<<"Second"<<endl;
  rep(i,1,k+1){
   // cout<<dp[i]<<endl; 
  }
}









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

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    long long N;
    cin >> N;
    const auto &res = prime_factorize(N);
    vector<long long> ko;
    for (auto p : res) {
        for (int i = 1; i <= p.second; ++i) ko.push_back(pow(p.first,i));
    }
    sort(ko.begin(),ko.end());
   long long sei = 0;
   for(long long i= 0;i<ko.size();i++){
     if(N%ko[i] == 0){
        sei++;
     	N = N/ko[i];
     }
   }
   cout<<sei;
}

Measured memory_bytes: 3580
import Data.Maybe
import Data.List
import Data.Bits
import qualified Data.ByteString.Char8 as BS

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

main = do
  [n,k] <- getIntList
  as <- getIntList
  print $ solve k n as

solve k n as = d + solve' cs where
  (bs, t:_) = break (k <) $ iterate (2*) 1
  s = t - 1
  d = sum [(a .|. s) `xor` s| a <- as]
  cs = snd $ mapAccumR f 0 (reverse bs)

  f :: Integer -> Integer -> (Integer, (Bool, Integer, Integer, Integer))
  f best b = (best + max v0 v1, (bitTest k, v0, v1, best)) where
    bitTest x = (x .&. b) /= 0
    cnt = genericLength $ filter bitTest as
    v0 = b * cnt
    v1 = b * (n - cnt)

solve' :: [(Bool, Integer, Integer, Integer)] -> Integer
solve' cs = foldr f 0 cs where
  f (False, v0, _, best) accum = v0 + accum
  f (True, v0, v1, best) accum
    | v0 >= v1 = w
    | otherwise = max w (v1 + accum)
    where
      w = v0 + best


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

#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}

int main(void){
    string s;
    cin>>s;
    cout<<(s=="ABC"?"ARC":"ABC")<<endl;
    return 0;
}

Measured memory_bytes: 3636
H,W = [int(i) for i in input().split()]
nes = [0] * H
for i in range(H) :
    li = list(input())
    nes[i] = li
lia = ["#"] * (W+2)
nes.append(lia)
nes.insert(0,lia)
for i in range(1,H+1) :
    nes[i].append("#")
    nes[i].insert(0,"#")
for i in range(H+2) :
    k = ''.join(nes[i])
    print(k)

Measured memory_bytes: 3064
n=int(input())
a=list(map(int,input().split()))
gray=brown=green=cyan=blue=yellow=orange=red=num=0
for i in range(n):
    if 1<=a[i]<=399:
        gray=1
    if 400<=a[i]<=799:
        brown=1
    if 800<=a[i]<=1199:
        green=1
    if 1200<=a[i]<=1599:
        cyan=1
    if 1600<=a[i]<=1999:
        blue=1
    if 2000<=a[i]<=2399:
        yellow=1
    if 2400<=a[i]<=2799:
        orange=1
    if 2800<=a[i]<=3199:
        red=1
    if 3200<=a[i]:
        num+=1
total=gray+brown+green+cyan+blue+yellow+orange+red
if total==0:
    print(1,num)
else:
    print(total,total+num)

Measured memory_bytes: 3064
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    C = read().split()
    ans = ''
    for i in range(3):
        ans += C[i][i]
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 22;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n; cin >> n;
  vi p(n);
  REP(i, n) {
    cin >> p[i];
  }

  sort(ALL(p));
  int ans = 0;
  REP(i, n-1) {
    ans += p[i];
  }
  ans += p[n-1]/2;
  cout << ans << endl;
}


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

using namespace std;

#define fastio cin.tie(NULL);cout.tie(NULL);ios_base::sync_with_stdio(0);
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MAXN 200005
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define endl '\n'
#define int long long

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <vi> matriz;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// auto timer_start = chrono::steady_clock::now().time_since_epoch().count();

int n, v;

matriz mult(matriz a, matriz b){
    matriz c (n + 5, vi(n + 5, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                c[i][j] = (c[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
            }
        }
    }
    return c;
}
 
matriz pow(matriz a, int p){
    if(p == 1) return a;
    if(p & 1) return mult(a, pow(a, p - 1));
    matriz b = pow(a, p / 2);
    return mult(b, b);
}

int32_t main(){
    // fastio
    cin >> n >> v;
    matriz grafo(n + 5, vi(n + 5, 0));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> grafo[i][j];
        }
    }
    
    int out = 0;
    matriz res = pow(grafo, v);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            out = (out + res[i][j]) % MOD;
        }
    }
    cout << out << endl;

    return 0;
}

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

int rec(int init, string circle, bool use, int n){
  int m = circle.size();
  bool f1 = true, f2 = true;
  for(int i=0;i<m;i++){
    if(circle[i]=='B')f1 = false;
    if(circle[i]=='G')f2 = false;
  }
  if(f1)return 0;
  if(f2)return m;

  int res = 0, rm = (init+n-1)%m;
  string tmp = circle;
  tmp.erase(tmp.begin() + rm);
  res = max(res, rec( rm%(m-1), tmp, use, n));

  if(!use){
    rm = (rm+1)%m;
    tmp = circle;
    tmp.erase(tmp.begin() + rm);
    res = max(res, rec( rm%(m-1), tmp, 1, n));
  }
  return res;
}

int main(){
  int T;
  cin >> T;
  while(T--){
    int n;
    string s;
    cin >> n >> s;
    cout << rec(0,s,0,n) << endl;
  }
}

Measured memory_bytes: 1320
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <stdio.h>
#include <string.h>
#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>
using namespace std;
typedef long long ll;


int main(int argc, char *args[]) {
	string s;
	int w;
	int i = 0;
	int counter = 1;
	cin >> s >> w;
	while (counter <= s.size()) {
		cout << s[0 + i * w];
		i++;
		counter = counter + w;
	}
	cout << endl;
}


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

using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<pair<long long, long long>> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second;

    sort(a.begin(), a.end());
    long long ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(m >= a[i].second)
        {
            ans += a[i].second * a[i].first;
            m -= a[i].second;
        }
        else
        {
            ans += m * a[i].first;
            m = 0;
            break;
        }
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 1792
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    int a, p; scan(a, p);

    int ans = (p + a * 3) / 2;
    writeln(ans);
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
long long d[60][60][3600],v[60],i,j,k,a,n,s;
int main()
{
    cin>>n>>a;
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=1;i<=n;i++)
        d[i][1][v[i]]++;

    for(i=2;i<=n;i++){
        for(j=1;j<=i;j++){
            int tr =0;
            for(k=1;k<=2500;k++)
                d[i][j][k] += d[i-1][j][k];
            for(k=v[i];k<=2500;k++){
                d[i][j][k]+=d[i-1][j-1][k-v[i]];

            }
        }
    }
    for(i=1;i<=n;i++)

        s+=d[n][i][a*i];
    cout<<s;
    return 0;
}


Measured memory_bytes: 84224
# !/usr/bin/pyhton3

import math

def solve(x, y):
    return math.sqrt(x*x + y*y)

if __name__ == "__main__":
    ans = 0

    n, d = list(map(int, input().split()))

    while n:
        x, y = list(map(int, input().split()))
        ans += 1 if solve(x, y) <= d else 0
        n -= 1

    print(ans)


Measured memory_bytes: 9168
def main():
    n = int(input())
    x = []
    for _ in range(n):
        a, b, c = map(int, input().split())
        x.append((a, b, c))
    dp0 = [0]*(n+1)
    dp1 = [0]*(n+1)
    dp2 = [0]*(n+1)
    for i in range(1,n+1):
        a, b, c = x[i-1]
        dp0[i] = max(dp1[i-1]+a, dp2[i-1]+a)
        dp1[i] = max(dp0[i-1]+b, dp2[i-1]+b)
        dp2[i] = max(dp0[i-1]+c, dp1[i-1]+c)
    print(max(dp0[n], dp1[n], dp2[n]))

if __name__ == "__main__":
    main()

Measured memory_bytes: 66776
n=int(input())
A=list(map(int,input().split(" ")))

base=10**9+7
s=0
for i in range(1,len(A),1):
    s=(s+A[i])%base
ans=0
for i in range(len(A)-1):
    ans=(ans+(A[i]*s))%base
    s=(s-A[i+1]+base)%base
print(ans)


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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}

template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

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

  ll k; cin >> k;
  ll now = 1;
  ll tmp = 7%k;

  vector<bool> sel(k, false);
  bool ok = false;
  int cnt = 0;
  while(1) {
    if(sel[tmp]) {
      break;
    }
    cnt++;
    if(tmp % k == 0) {
      ok = true;
      break;
    } else {
      sel[tmp] = true;
      now *= 10;
      now %= k;
      tmp = (tmp + 7 * now % k) % k;
    }
  }
  cout << (ok ? cnt : -1) << endl;

}








Measured memory_bytes: 3744
var
x,i:longint;
s:string;
begin
readln(s);
readln(x);
for i:=1 to length(s) do
 if s[i]='1' then
 begin
 dec(x);
  if x=0 then
  begin
  writeln(1);
  halt;
  end;
 end
 else
 begin
 writeln(s[i]);
 halt;
 end;
end.

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

using namespace std;

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

using ll = long long;
using ull = unsigned 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; cin >> n;
  vector<int> v(n);
  cin >> v;
  int sum = 0;
  int x = 1;
  for(int i = 0; i < n; ++i){
    if(v[i] % 2 == 0){
      sum += pow(3,n-i-1)*x;
      x*=2;
    }else{    
      sum += pow(3,n-i-1)*2*x;
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 3956
//参考：http://ehafib.hatenablog.com/entry/2015/12/23/164517
//インクルード
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

signed main(){
  int K, N;
  cin >> K >> N;
  int A[N];
  for (int i = 0; i < N; i++) cin >> A[i];

  int dmax = 0;
  for (int i = 0; i < N - 1; i++) {
    if (A[i + 1] - A[i] > dmax) dmax = A[i + 1] - A[i];
  }
  if (K + A[0] - A[N - 1] > dmax) dmax = K + A[0] - A[N - 1];

  cout << K - dmax << endl;
  return 0;
}

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

#define int long long

int X, Y, Z;
ll A[100010], B[100010], C[100010];

signed main(void) {
	cin >> X >> Y >> Z;
	rep(i, X + Y + Z) cin >> A[i] >> B[i] >> C[i];

	vector<pair<ll, int>> v;
	rep(i, X + Y + Z) {
		v.pb(make_pair(A[i] - B[i], i));
	}
	sort(all(v)); reverse(all(v));


	ll sumF = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int> >> pA;
	vector<ll> memoF;
	rep(i, X) {
		int idx = v[i].se;
		sumF += A[idx];
		pA.push(mp(A[idx] - C[idx], idx));
	}
	memoF.pb(sumF);
	reps(i, X, X + Z) {
		int idx = v[i].se;
		pA.push(mp(A[idx] - C[idx], idx));
		int minidx = pA.top().se; pA.pop();
		sumF += A[idx] - A[minidx] + C[minidx];
		memoF.pb(sumF);
	}

	ll sumB = 0;
	priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int> >> pB;
	vector<int> memoB;
	for (int i = X + Y + Z - 1; i > X + Z - 1; --i) {
		int idx = v[i].se;
		sumB += B[idx];
		pB.push(mp(B[idx] - C[idx], idx));
	}
	memoB.pb(sumB);
	for (int i = X + Z - 1; i >= X; --i) {
		int idx = v[i].se;
		pB.push(mp(B[idx] - C[idx], idx));
		int minidx = pB.top().se; pB.pop();
		sumB += B[idx] - B[minidx] + C[minidx];
		memoB.pb(sumB);
	}
	reverse(all(memoB));

	ll ans = 0;
	rep(i, memoF.size()) {
		chmax(ans, memoF[i] + memoB[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

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

int main(){
    ll n, p; cin >> n >> p;
    ll ans = 1;
    ll div = 2;
    if(n==1){
        ans = p;
    }
    else{
        while(p>=pow(div, n)){
            ll m=0;
            while(p%div==0){
                m++;
                p = p/div;
            }
            if(m>=n)ans*=pow(div, m/n);
            div++;
        }
    }
    cout << ans << endl;
}

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

int main(){
  int n;
  string s;
  cin >> n >> s;
  rep(i, s.size()){
    char c='A'+(s[i]-'A'+n)%26;
    cout << c;
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 3648
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int  fa[200008],fb[200008],fc[200008];
int main(){
  int n,m;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
  	scanf("%d",fa+i);
  	fb[i]=fa[i];
  }
  sort(fb,fb+n);
  long long sum=0,s=1;
  for(int i=1;i<n;i++){
  	if(fb[i]==fb[i-1])
  	s++;
  	else{
  		fc[fb[i-1]]=s;
  	   sum+=(s-1)*s/2;
		 s=1;	
	}
  }
  fc[fb[n-1]]=s;
  sum+=(s-1)*s/2;
  for(int i=0;i<n;i++){
  	int x=fc[fa[i]];
  	printf("%lld\n",sum-x+1);
  }
}



Measured memory_bytes: 4480
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<string> s(n);
    for(int i=0;i<n;i++)cin>>s[i];

    vector<vector<int>> cnt(n,vector<int>(26));
    vector<int> mincnt(26);
    fill(mincnt.begin(),mincnt.end(),100);
    for(int i=0;i<n;i++){
        for(int j=0;j<s[i].size();j++){
            cnt[i][s[i][j]-'a']++;
        }
        for(int j=0;j<26;j++){
            mincnt[j]=min(mincnt[j],cnt[i][j]);
        }
    }

    for(int i=0;i<26;i++){
        if(mincnt[i]==0)continue;
        for(int j=0;j<mincnt[i];j++){
            cout<<char('a'+i);
        }
    }
    cout<<endl;
}

Measured memory_bytes: 256
import sys

N = int(sys.stdin.readline().strip())
D = [0] + [int(x) for x in sys.stdin.readline().strip().split()]

def kei(xs, n):
    xs = xs + [x + 24 for x in xs]
    m1 = min(abs(n - x) for x in xs)
    m2 = min(abs((24 - n) - x) for x in xs)
    if m1 >= m2:
        return n, m1
    else:
        return 24 - n, m2

def calc(D):
    D.sort()
    #print(D)
    n = len(D)
    if N > 24:
        return 0
    if D[1] == 0:
        return 0
    xs = D[:2]
    D = D[2:]
    r = xs[1] - xs[0]
    for d in D:
        #print(xs, d)
        c, m = kei(xs, d)
        #print("r", c, m)
        if m < r:
            r = m
        xs += [c]
    return r



print(calc(D))


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

using namespace std;
typedef long long ll;
ll mod = 1000000007;

vector<vector<ll>> adj;
vector<ll> b;
vector<ll> w;

ll solve(ll curr, ll prev = -1) {
    for(auto next : adj[curr]) {
        if(next == prev) continue;

        solve(next, curr);

        w[curr] *= b[next] + w[next];
        b[curr] *= w[next];

        w[curr] %= mod;
        b[curr] %= mod;
    }

    return (w[curr] + b[curr]) % mod;
}

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

    adj.resize(n);
    b.resize(n,1);
    w.resize(n,1);

    for(ll i = 0; i < n-1; i++) {
        ll n1, n2;
        cin >> n1 >> n2;
        n1--; n2--;
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
    }

    cout << solve(0) << endl;
}


Measured memory_bytes: 12800
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>

using namespace std;


#include <math.h> 


int main() {

	int N, Q;
	cin >> N;
	vector<int>A(N);
	map<int, int> M1;
	int64_t total = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		total += A[i];
		M1[A[i]]++;
	}


	cin >> Q;
	vector<int64_t> result(Q);
	for (int i = 0; i < Q; i++) {
		int a, b;
		int64_t c, d;
		cin >> a >> b;
		c = (b - a) * M1[a];
		M1[b] += M1[a];
		M1[a] = 0;

		total += c;

		result[i] = total;

	}
	for (int i = 0; i < Q; i++) {
		cout << result[i] << endl;
	}

	return 0;

}

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

#define ll long long
#define v vector 

const ll mod = 1e9 + 7;

ll fastpow(ll x, ll n) {
    ll res = 1;
    while (n != 0) {
        if(n & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        n = (n >> 1);
    }
    return res;
}

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

    ll n, c;
    cin >> n >> c;
    v<ll> a(n), b(n);
    for(ll i = 0; i < n; i ++) {
        cin >> a[i];
    }
    for(ll i = 0; i < n; i ++) {
        cin >> b[i];
    }
    v<v<ll>> preComp(n, v<ll> (c+1));
    for(ll i = 0; i < n; i ++) {
        for(ll j = 0; j <= c; j ++) {
            ll val = 0;
            for(ll k = a[i]; k <= b[i]; k ++) {
                val = (val + fastpow(k, j)) % mod;
            }
            preComp[i][j] = val;
        }
    }

    v<v<ll>> dp(n, v<ll> (c+1));
    for(ll i = 0; i < n; i ++) {
        if(i == 0) {
            for(ll j = 0; j <= c; j ++) {
                dp[i][j] = preComp[i][j];
            }
        }
        else {
            for(ll j = 0; j <= c; j ++) {
                ll tot = j;
                for(ll k = 0; k <= tot; k ++) {
                    ll first = k;
                    ll second = tot-k;
                    dp[i][j] = (dp[i][j] + ((dp[i-1][first] * preComp[i][second]) % mod)) % mod;
                }
            }
        }
    }
    cout << dp[n-1][c] << endl;

    return 0;
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a[100000],b[10000];
  int t = 1,m = 1;
  a[0] = 2;
  for(int i = 3;i <55555;i+=2)
  {
    int k = 0;
    for(int p = 3;p <=sqrt(i);p+=2)
    {
      if(i%p == 0)
      {
        k = 1;
        break;
      }
    }
    if(k == 0)
    { 
      a[t] = i;
      t++;
    }
  }
  for(int p = 0;p<20000;p++)
  {
  	if(a[p]%10 == 1)
	{
		b[m] = a[p];
		m++;
	}
  }
  int N;
  cin >> N;
  cout << 2 << " ";
  for (int q = 1;q<N;q++)
  {
  	cout << b[q] << " ";
  }
  return 0;
}


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

int main() {
	int mat[51][51] = {};
	int pos[51][51] = {};
	int H, W;
	int i, j;
	cin >> H >> W;
	char s;
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			cin >> s;
			if (s == '#')pos[i][j] = 1;
			else pos[i][j] = 0;
		}
		cout << endl;
	}

	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (pos[i][j] == 0)continue;
			else {
				if (i + 1 <= H && pos[i+1][j] == 1)mat[i+1][j] = 1;
				if (i - 1 >= 1 && pos[i-1][j] == 1)mat[i-1][j] = 1;
				if (j + 1 <= W && pos[i][j+1] == 1)mat[i][j+1] = 1;
				if (j - 1 >= 1 && pos[i][j-1] == 1)mat[i][j-1] = 1;
			}
		}
	}

	for (i = 1; i <= H; i++)for (j = 1; j <= W; j++) {
		if (mat[i][j] != pos[i][j]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;

}

Measured memory_bytes: 256