akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

int main(){
    string s;
    cin >> s;
    int n = s.size();

    // dp[i + 1][j] : i 文字目までで状態 j となるものの総数
    ll dp[n + 1][4];
    // 初期化
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i < n; i++){
        if (s[i] == 'A' || s[i] == '?'){
            (dp[i + 1][0] += dp[i][0]) %= MOD;
            (dp[i + 1][1] += dp[i][1]) %= MOD;
            (dp[i + 1][2] += dp[i][2]) %= MOD;
            (dp[i + 1][3] += dp[i][3]) %= MOD;

            (dp[i + 1][1] += dp[i][0]) %= MOD;
        }

        if (s[i] == 'B' || s[i] == '?'){
            (dp[i + 1][0] += dp[i][0]) %= MOD;
            (dp[i + 1][1] += dp[i][1]) %= MOD;
            (dp[i + 1][2] += dp[i][2]) %= MOD;
            (dp[i + 1][3] += dp[i][3]) %= MOD;

            (dp[i + 1][2] += dp[i][1]) %= MOD;
        }

        if (s[i] == 'C' || s[i] == '?'){
            (dp[i + 1][0] += dp[i][0]) %= MOD;
            (dp[i + 1][1] += dp[i][1]) %= MOD;
            (dp[i + 1][2] += dp[i][2]) %= MOD;
            (dp[i + 1][3] += dp[i][3]) %= MOD;

            (dp[i + 1][3] += dp[i][2]) %= MOD;
        }
    }

    cout << dp[n][3] << endl;

    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
using namespace std;
int main(){
  long int N ,M, m;
  cin >> N >> M;

  m = M/2;

  if(m <= N)
    cout << m << endl;
  else{
    m = m - N;
    m /=2;
    cout << N + m << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;

string g[2005];
int lDP[2005][2005];
int rDP[2005][2005];
int uDP[2005][2005];
int dDP[2005][2005];
int r, c;

void solve() {
  cin >> r >> c;
  for(int i = 0; i < r; i++) {
    cin >> g[i];
  }
  for(int i = 0; i < r; i++) {
    lDP[i][0] = -1;
    for(int j = 0; j < c; j++) {
      if(g[i][j] == '#') {
        lDP[i][j] = j;
      }
      else if(j > 0) {
        lDP[i][j] = lDP[i][j-1];
      }
    }
    rDP[i][c-1] = c;
    for(int j = c-1; j >= 0; j--) {
      if(g[i][j] == '#') {
        rDP[i][j] = j;
      }
      else if(j < c-1) {
        rDP[i][j] = rDP[i][j+1];
      }
    }
  }
  for(int j = 0; j < c; j++) {
    uDP[0][j] = -1;
    for(int i = 0; i < r; i++) {
      if(g[i][j] == '#') {
        uDP[i][j] = i;
      }
      else if(i > 0) {
        uDP[i][j] = uDP[i-1][j];
      }
    }
    dDP[r-1][j] = r;
    for(int i = r-1; i >= 0; i--) {
      if(g[i][j] == '#') {
        dDP[i][j] = i;
      }
      else if(i < r-1) {
        dDP[i][j] = dDP[i+1][j];
      }
    }
  }
  int ret = 0;
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      if(g[i][j] == '#') continue;
      int cand = 0;
      cand += i - uDP[i][j];
      cand += dDP[i][j] - i;
      cand += j - lDP[i][j];
      cand += rDP[i][j] - j;
      ret = max(ret, cand);
    }
  }
  cout << ret-3 << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 67328
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long int lli;

int main() {
	lli X, Y;
	cin >> X >> Y;

		lli t = Y / X;
	int max = 0;
	while (t>0) {
		max += 1;
		t = t / 2;
	}
	cout << max;
}

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

int main()
{
    int i, a, b;
    cin >> a >> b;
    if (a <= b)
    {
        for (i = 0; i < b; i++)
        {
            cout << a;
        }
    }
    else
    {
        for (i = 0; i < a; i++)
        {
            cout << b;
        }
    }
    cout << endl;
}

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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

void dump(int i, int j){
  if(!!( i & (1<<j) )) cout << '+';
  else cout << '-';
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  rep(i,1<<3){
    int ans = (int)(s[0] - '0');
    rep(j,3){
      if(!!( i & (1<<j) )){
         ans += (int)(s[j+1] - '0');
      }else{
        ans -=  (int)(s[j+1] - '0');
      }
    }
    if(ans == 7){
      cout << s[0];
      rep(j,3){
        dump(i,j);
        cout << s[j+1];
      }
      cout << "=7" << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;
	cin>>n;
	ll ans=0;
	for(ll i=1;i<=n;i++){
		if(i%3!=0&&i%5!=0){
			ans+=i;
		}
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 3604
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);const tn=():number=>{const a=input[0];input.shift();return Number(a)};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{const a=input[0];input.shift();return String(a)};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const tc=():string=>{let a=input[0].split('');const b=a[0];a.shift();if(a.length>0){input[0]=a.join('')}else{input.shift()}return String(b)};const tcc=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(tc())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1];}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const objvs =(a)=>{const b=[];for(const v in a){b.push(a[v])}return b};
const main=()=>{
  let n=tn()
  let nr=tnn(n)
  to(max(...nr)-min(...nr))
}
main()


Measured memory_bytes: 7372
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static double ans;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		while(true) {

			int r = sc.nextInt();
			int n = sc.nextInt();

			if((n|r)==0) {
				break;
			}

			//[x軸][y軸]
			boolean[][] plusArea = new boolean[20][20];
			boolean[][] minusArea = new boolean[20][20];

			for(int i = 0;i<n ; i++) {
				int startX = sc.nextInt();
				int endX = sc.nextInt();
				int height = sc.nextInt();

			if(startX >= 0) {
				for(int h = 0;h<height ; h++) {
					for(int j = startX; j<endX; j++) {
						plusArea[j][h] = true;
					}
				}
			}else if (endX <= 0) {
				startX *= -1;
				endX *= -1;
				for(int h = 0;h<height ; h++) {
					for(int j = endX; j< startX; j++) {
						minusArea[j][h] = true;
					}
				}
			}else {
				startX *= -1;
				for(int h = 0;h<height ; h++) {
					for(int j = startX-1; j>=0; j--) {
						minusArea[j][h] = true;
					}
					for(int j = 0; j<endX; j++) {
						plusArea[j][h] = true;
					}
				}
			}
			}

			//x軸、y軸。象限両用
			double dist[][] = new double[20][20];

			for(int i = 0;i<20 ; i++) {
			Arrays.fill(dist[i], Double.MAX_VALUE);
			}

			//全ての升について必要になる時間を出す
			for(int i = 0;i<r ; i++) {
				for(int j = 0;j<20 ; j++) {

					if(i == 0) {
						dist[i][j] = j;
						continue;
					}else if(j==0) {
						dist[i][j] = j;
					}

					if(j == 0) {
						dist[i][j] = r-Math.sqrt(r*r-i*i);
						continue;
					}
					dist[i][j] = dist[i][j-1]+1;
				}
			}
			ans = 20;
			for(int i = 0;i<r ; i++) {
				for(int j = 0;j<20 ; j++) {
					if(!plusArea[i][j] || !minusArea[i][j]) {
						if(ans > dist[i][j]) {
							ans = dist[i][j];
						}
					}
				}
			}

			System.out.println(ans);

		}


	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}
}


Measured memory_bytes: 36988
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
const int MOD = 1000000007; 

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> as(n+1);
    rep(i, n) cin >> as[i+1];
    vector<ll> rs(n+1, -1);
    int st = 1;
    int ord = 0; 
    while (rs[st] == -1) {
        rs[st] = ord;
        st = as[st];
        ++ord;
        if (ord == k) {
            cout << st << endl;
            return 0;
        }
    }
    k -= rs[st];
    int res = k % (ord-rs[st]);
    rep(i, res) st = as[st];
    cout << st << endl;
    return 0;
}

Measured memory_bytes: 6348
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeSet;

import org.omg.Messaging.SyncScopeHelper;

public class Main {
	Scanner sc = new Scanner(System.in);
	public static void main(String[] args){
		new Main();
	}
	public Main(){
		new Test_100().doIt();
	}
	class Test_100{
		void doIt() {
			int X = sc.nextInt();
			int A = sc.nextInt();
			int B = sc.nextInt();
			int ans = (X - A) % B;
			System.out.println(ans);
		}
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		for(int a=8;a>=0;a--)for(int i=0;i<=a;i++)s[i]=(char)((s[i]-'0'+s[i+1]-'0')%10+'0');
		cout<<s[0]<<endl;
	}
}

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

#define fi first
#define se second
#define forn(i,n) for(int i=0; i< (int)n; ++i)
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el
#define ri(n) scanf("%d",&n)

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

const ll INF = LONG_LONG_MAX;
const int MAXN = 1e5+200;
const int mod = 1e9 +7;

string digits;
int d;
int n;
int dp[10010][2][110];  // idx - menor - sum

int go(int idx, int menor, int sum){
    if(idx==n) return (sum==0);
    int &r = dp[idx][menor][sum];
    if(r!=-1) return r;
    r= 0;
    int k= ((!menor) ? digits[idx]-'0' : 9);
    for(int i= 0; i<= k; ++i){
        if(k==i && !menor){
            r+= go(idx+1, menor, (sum+i)%d);
        }else{
            r+= go(idx+1, 1, (sum+ i)%d);
        }
        r%=mod;
    }
    return r;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>> digits>> d;
    memset(dp, -1, sizeof dp);
    n= digits.size();
    cout<<(go(0,0,0)-1+mod)%mod<<el;
}



Measured memory_bytes: 9600
N = int(input())
arr = list(map(int, input().split()))
new_arr = sorted(arr)

bob   = 0
alice = 0

for i in range(len(new_arr)):
    if i % 2 ==0:
        alice += new_arr[i]
    elif i % 2 ==1:
        bob += new_arr[i]

print(abs(alice-bob))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n,L;
int main(){
	scanf("%d%d",&n,&L);
	int S=0,Mn=1e8;
	for(int i=1;i<=n;i++){
		S+=L+i-1;
		if(abs(L+i-1)<abs(Mn))Mn=L+i-1;
	}
	printf("%d\n",S-Mn);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int w,s;
  cin>>s>>w;
  if(w>=s)
  {
      cout<<"unsafe"<<endl;
  }
  else cout<<"safe"<<endl;

}

Measured memory_bytes: 3640
#include<stdio.h>

int max(int a,int b){
 if(a > b)return a;
 return b;
}


int main(){
 int x,y,s;
 int P[10][10];
 int cnt=0;
 int maxi=-1;
 int i,j;

 for(i=0;i<=9;i++){
  for(j=0;j<=9;j++){
    P[i][j]=0;
  }
 }


 while(scanf("%d,%d,%d",&x,&y,&s)!=EOF){
/*  if(s==0)break;*/
  switch(s){

   case 1:for(i=x-1;i<=x+1;i++){
           if(i>=0 && i<=9)
             P[i][y]++;
          }

           for(i=y-1;i<=y+1;i++){
           if(i>=0 && i<=9)
             P[x][i]++;
          }

          P[x][y]--;

          break;

   case 2:for(i=y-1;i<=y+1;i++){
            for(j=x-1;j<=x+1;j++){
               if(i>=0 && i<=9 && j>=0 && j<=9)P[j][i]++;
            }
           }

           break;

   case 3:for(i=y-1;i<=y+1;i++){
            for(j=x-1;j<=x+1;j++){
               if(i>=0 && i<=9 && j>=0 && j<=9)P[j][i]++;
            }
           }

           if(x-2 >=0)P[x-2][y]++;
           if(x+2 <=9)P[x+2][y]++;
           if(y-2 >=0)P[x][y-2]++;
           if(y+2 <=9)P[x][y+2]++;

           break;

  }

 }

 for(i=0;i<=9;i++){
  for(j=0;j<=9;j++){
    if(P[i][j]==0)cnt++;
    maxi=max(maxi,P[i][j]);
  }
 }

 printf("%d\n%d\n",cnt,maxi);

 return 0;
}


Measured memory_bytes: 2016
# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    n = int(input())

    # See:
    # https://www.youtube.com/watch?v=Ommfmx2wtuY
    if (n == 10) or (n == 100) or (n == 1000) or (n == 10000) or (n == 100000):
        print(10)
    else:
        print(sum(list(map(int, list(str(n))))))


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <stdio.h>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional> //operator[]
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

signed main(){
    int n; cin >> n;
    char s[n][n];
    rep(i,n)rep(j,n) cin >> s[i][j];
    
    int ans=0;
    rep(t,2*n-1){
        bool flg=0;
        rep(i,n){
            rep(j,n){
                int x=(j+t)%n;
                int y=(i-t+1000*n)%n;

                if(s[i][j] != s[x][y]){
                    flg=1; break;
                }
            }
            if(flg) break;
        }
        if(flg) continue;
        if(t>=n) ans+=(2*n-t-1);
        else ans+=(t+1);
    }
    cout << ans << endl;
}


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

double d(double a)
{
	double b;
	b = a * 2;
	return b;
}
double t(double a)
{
	double b;
	b = a / 3;
	return b;
}
int main()
{
	double n;
	
	while (cin >> n)
	{
		double a = 0;
		double q[10];
		q[0] = n;
		for (int i = 0; i < 10; i++)
		{
			if (i % 2 == 0)
			{
				q[i + 1] = d(q[i]);
			}
			if (i % 2 == 1)
			{
				q[i + 1] = t(q[i]);
			}
		}
		for (int i = 0; i < 10; i++)
		{
			a = q[i] + a;
		}
		cout << fixed << setprecision(8) << a << endl;
	}


	return 0;
}


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

from bisect import bisect
from bisect import bisect_right
from bisect import bisect_left
from bisect import insort
from bisect import insort_right
from bisect import insort_left 

def scores(c, s, t, t_days):
    last = [0] * 26
    D = len(t)
    t_score = []
    # print([s[d*26+i] for d, i in enumerate(t)])
    s_score = sum([s[d*26+i] for d, i in enumerate(t)])
    for i, days in enumerate(t_days):
        last = 0
        score = 0
        for d in days[1:]:
            delta = d - last - 1
            # print(i, d, delta)
            score += delta * (delta + 1)
            last = d
        # print(i, score)
        score = score * c[i] // 2
        t_score.append(score)
    # print(t_score)
    return s_score - sum(t_score)


def main():
    D, *cs = map(int, read().split())
    c = cs[:26]
    se = 26+26*D
    s = cs[26:se]
    te = se+D
    t = [x-1 for x in cs[se:te]]
    M = cs[te]
    dq = [(d, q-1) for d, q in zip(cs[te+1::2], cs[te+2::2])]

    t_days = [[0] for i in range(26)]
    for d, x in enumerate(t, start=1):
        t_days[x].append(d)
    for i in range(26):
        t_days[i].append(D+1)
    # print(t_days)

    v = scores(c, s, t, t_days)
    # print(v)
    ans = []
    for d, q in dq:
        dd = d-1
        bq = t[dd]
        t[dd] = q
        v += s[dd*26+q] - s[dd*26+bq]
        days_q = t_days[q]
        days_bq = t_days[bq]
        qi = bisect_left(days_q, d)
        bqi = bisect_left(days_bq, d)
        # print(bq, bqi, q, qi)

        # 削除することで増える分
        da = days_bq[bqi+1] - days_bq[bqi-1] - 1
        db1 = days_bq[bqi+1] - days_bq[bqi] - 1
        db2 = days_bq[bqi] - days_bq[bqi-1] - 1
        bqp = da * (da + 1) - (db1*(db1+1) + db2*(db2+1))
        # 追加することで減る分
        db = days_q[qi] - days_q[qi-1] - 1
        da1 = days_q[qi] - d - 1
        da2 = d - days_q[qi-1] - 1
        qp = db * (db + 1) - (da1*(da1+1) + da2*(da2+1))

        # print((bqp * c[bq] // 2))
        # print((qp * c[q] // 2))
        delta = (qp * c[q] // 2) - (bqp * c[bq] // 2)

        # print(days_bq, days_q)
        insort_left(days_q, d)
        del(days_bq[bqi])
        # print(days_bq, days_q)
        v += delta
        # print(v, delta)
        ans.append(v)
        # t_days[bq].remove(bq)

        # qの不満度が減る分



        # last = 0
        # score = 0
        # for d in t_days[q] + [D+1]:
        #     delta = d - last - 1
        #     # print(i, d, delta)
        #     score += delta * (delta + 1)
        #     last = d
        # # print(i, score)
        # score = score * c[q] // 2


    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

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

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define F(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define endl '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


const int N = 4004; 

string s;
int n, cnt[N][3];
int mdf(char x)  {
	if (x == 'R') return 0;
	if (x == 'G') return 1;
	else return 2; 
} 

bool ok(int a, int b, int c) {
	if (a > n || b > n || c > n) return 0; 
	return mdf(s[a]) != mdf(s[b]) && mdf(s[b]) != mdf(s[c]) && mdf(s[c]) != mdf(s[a]);
}
void solve() {
	cin >> n >> s; s = " " + s;
	
	F(i, 1, n) {
		memcpy(cnt[i], cnt[i-1], sizeof(cnt[i-1]));
		++cnt[i][mdf(s[i])];
	}
	
	ll tot = 0;
	F(i, 1, n) {
		if (s[i] == 'R') {
			tot += 1ll * cnt[i-1][1] * (cnt[n][2] - cnt[i][2]);
			tot += 1ll * cnt[i-1][2] * (cnt[n][1] - cnt[i][1]);
		} else if (s[i] == 'G') {
			tot += 1ll * cnt[i-1][0] * (cnt[n][2] - cnt[i][2]);
			tot += 1ll * cnt[i-1][2] * (cnt[n][0] - cnt[i][0]);
		} else if (s[i] == 'B') {
			tot += 1ll * cnt[i-1][1] * (cnt[n][0] - cnt[i][0]);
			tot += 1ll * cnt[i-1][0] * (cnt[n][1] - cnt[i][1]);
		}
		F(j, 1, i-1) if (ok(j, i, i + (i-j))) --tot;
	}
	cout << tot << endl;
}





int main() {
	ios::sync_with_stdio(false);
	cout << fixed;

#ifdef LOCAL
	double cl = clock();
#endif

	int T = 1;
	while (T--) solve();

#ifdef LOCAL
  cerr << "Time elapsed: " << (clock() - cl) / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}




Measured memory_bytes: 3700
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int p[1010];
string str;
stringstream ss;
int m,n;
bool one;

void clear(int k){
	if(one)return;
	else p[k]=0;
}

int next(int k){
	k++;
	while(1){
		if(k>m)k=1;
		if(p[k]==1)break;
		k++;
	}
	return k;
}

int main() {
	while(cin>>m>>n,m){
		one=false;
		int i,j,k;
		k=1;
		for(i=1;i<=m;i++)p[i]=1;
		for(i=1;i<=n;i++){
			int count=0;
			for(j=1;j<=m;j++){
				if(p[j])count++;
			}
			if(count==1)one=true;
			cin>>str;
			if(i%15==0){
				if(str!="FizzBuzz"){
					clear(k);
				}
				k=next(k);
			}else if(i%3==0){
				if(str!="Fizz"){
					clear(k);
				}
				k=next(k);
			}else if(i%5==0){
				if(str!="Buzz"){
					clear(k);
				}
				k=next(k);
			}else{
				int x;
				for(j=0;j<str.size();j++){
					if(str[j]<'0'||'9'<str[j]){
						break;
					}
				}
				if(j!=str.size()){
					clear(k);
				}else{
					x=0;
					for(j=0;j<str.size();j++){
						x=x*10+str[j]-'0';
					}
					if(i!=x)clear(k);
				}
				k=next(k);
			}
		}
		bool first=true;
		for(i=1;i<=m;i++){
			if(p[i]==1){
				if(first){
					cout<<i;
					first=false;
				}else{
					cout<<" "<<i;
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

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

int main(void){
    char a[4];
    cin >> a;
    sort(a,a+4);
    int b = 0;
    if(a[0] != a[1])++b;
    if(a[1] == a[2])++b;
    if(a[2] != a[3])++b;
    if(b == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	
	a := make([]int, n)
	
	for i := range a {
		fmt.Scan(&a[i])
	}
	sort.Ints(a)

	ans := 1
	for i := range a {
		if a[i] == 0 {
			ans = 0
			break
		}
		if ans > 1e18/a[i] {
			ans = -1
			break
		}
		ans *= a[i]
	}
	fmt.Println(ans)
}

Measured memory_bytes: 6324
//minimum operations to reach y from x
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long

void solve()
{
	ll n,d;
	cin>>n>>d;
	vector<ll> X(n),Y(n);
	int cnt=0;
	for(int j=0;j<n;j++)
	{
		cin>>X[j]>>Y[j];
	}
	for(int j=0;j<n;j++)
	{
		ll a=pow(X[j],2)+pow(Y[j],2);
		if(sqrt(a)<=d)
		cnt++;
	}
	cout<<cnt<<endl;
}

int main()
{
	int t;
	t=1;
	while(t--)
	solve();
}

Measured memory_bytes: 6428
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int dp[n+1][4];
    int a,b,c;
    cin>> a >> b >> c;
    dp[1][1]=a;
    dp[1][2]=b;
    dp[1][3]=c;
    for(int i=2;i<=n;i++){
        cin >> a >> b >> c;
        dp[i][1]=max(dp[i-1][2]+a,dp[i-1][3]+a);
        dp[i][2]=max(dp[i-1][1]+b,dp[i-1][3]+b);
        dp[i][3]=max(dp[i-1][1]+c,dp[i-1][2]+c);
    }
    cout << max(dp[n][1],max(dp[n][2],dp[n][3])) << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)  //  repマクロ
#define leng(n) (int)(log10(n)+1)  //  桁数
using namespace std;

signed main() {
  string n;
  cin >> n;
  if (n[0]==n[1]) cout << "Bad" << endl;
  else if (n[1]==n[2]) cout << "Bad" << endl;
  else if (n[2]==n[3]) cout << "Bad" << endl;
  else cout << "Good" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
vector <long long> tree;

long long query (int v, int start, int end, int l, int r)
{
	if (r < start || l > end)
		return 0;
	
	if (l <= start && r >= end)
		return tree[v];
	
	int mid = (start + end)/2;
	return max(query(2*v, start, mid, l, r), query(2*v + 1, mid + 1, end, l, r));
}

void update (int v, int start, int end, int index, long long val)
{
	if (start == end) tree[v] = val;
	else
	{
		int mid = (start + end)/2;
		if (index <= mid)
			update(2*v, start, mid, index, val);
		else 
			update(2*v + 1, mid + 1, end, index, val);
		tree[v] = max(tree[2*v], tree[2*v + 1]);
	}
}

int main() 
{
	int n;
	cin >> n;
	long long h[n + 1], a[n + 1];
	tree.resize(4*n + 1);
	
	for (int i = 1; i <= n; i++)
		cin >> h[i];
		
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	for (int i = 1; i <= n; i++)
	{
		long long q = query(1, 1, n, 1, h[i] - 1);
		update(1, 1, n, h[i], q + a[i]);
	}
	cout << query(1, 1, n, 1, n);
}

Measured memory_bytes: 9600
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> A(N), B(M);
    rep(i, N) { cin >> A[i]; }
    rep(i, M) { cin >> B[i]; }
    for(int x = 0; x <= N - M; x++) {
        for(int y = 0; y <= N - M; y++) {
            int flag = 1;
            for(int i = 0; i < M; i++) {
                for(int j = 0; j < M; j++) {
                    if(A[y + i][x + j] != B[i][j])
                        flag = 0;
                }
            }
            if(flag == 1) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

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

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

	vector<int> s;
	inputVector(s, N);

	int sum = 0;
	rep(i, N) sum += s[i];

	if (sum % 10) {
		cout << sum << endl;
		return 0;
	}

	sort(all(s));

	rep(i, N) {
		if (s[i] % 10) {
			cout << sum - s[i] << endl;
			return 0;
		}
	}

	cout << 0 << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	

    public static void main(String[] args) {
		
    	Scanner s = new Scanner(System.in);
    	int k = s.nextInt();
    	int a = s.nextInt();
    	int b = s.nextInt();
    	
    	int flag=0;
    	for(int i=a;i<=b;i++) {
    		if(i%k==0) {
    			System.out.println("OK");
    			flag=1;
    			break;
    		}
    	}
    	if(flag==0) {
    		System.out.println("NG");
    	}
	}
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

typedef long long ll;
#define INF 1e9

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

ll N, M;

int main(){
  cin >> N >> M;

  if(2*N >= M){
    cout << M / 2 << endl;
  }
  else{
    cout << N + (M-2*N)/4 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int N;
	char S[37564];
	int i;

	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%37567s", S) != 1) return 1;

	for (i = 0; S[i] != '\0'; i++) {
		putchar('A' + (S[i] - 'A' + N) % 26);
	}
	putchar('\n');
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int main(void)
{
    int n;
    cin >> n;
    vector<vector<int>> tree(n);

    REP(i,n-1){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    vector<ll> c(n);
    REP(i,n){
        cin >> c[i];
    }
    
    vector<int> color(n,0);
    queue<int> s;
    vector<ll> vc(n);
    sort(all(c),greater<ll>());
    vc[0] = c[0];
    s.push(0);
    color[0]++;
    int cnt = 0;
    while(!s.empty()){
        int v = s.front();
        s.pop();
        REP(i,tree[v].size()){
            int child = tree[v][i];
            if(color[child] == 0){
                cnt++;
                vc[child] = c[cnt];
                color[child]++;
                s.push(child);
            }
        }
    }

    ll sum = 0;
    FOR(i,1,n){
        sum += vc[i];
    }

    cout << sum << endl;
    REP(i,n-1){
        cout << vc[i] << " ";
    }

    cout << vc[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
 
int main(){
  int N;
  cin>>N;
  VL C(N-1),S(N-1),F(N-1);
  rep(i,N-1) cin>>C[i]>>S[i]>>F[i];
  rep(i,N-1){
    ll ans=S[i]+C[i];
    rep(j,N-2-i){
      ans+=(max(ans,S[i+1+j])+F[i+1+j]-1)/F[i+1+j]*F[i+1+j]-ans+C[i+1+j];
    }
    cout<<ans<<endl;
  }
  cout<<0<<endl;
}

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

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

long long MOD = 1000000000 + 7;

int N;
string ALPHA = "abcdefghijklmn";

void solve(string s, char c){
  if(s.size() < N){
    for(char i = 'a'; i <= c+1; i++){
      solve(s + i, (i == c+1 ? (c+1) : c));
    }
  } else { 
    cout << s << endl;
  }
}

int main(){
  cout << setprecision(10);
  cin >> N;
  string s = "";
  solve("a", 'a');

  cerr  << (char)('a' + 1) << endl;

}


Measured memory_bytes: 1536
# _*_ coding:utf-8 _*_
#  Atcoder_nikkei2019_qual_Contest-A
#  TODO https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_a

def solveProblem(allPerson,subNewsA,subNewsB):
	subNewsA+subNewsB-allPerson

	answer = min(subNewsA,subNewsB),max(0,subNewsA+subNewsB-allPerson)
	return answer


if __name__ == '__main__':
	N,A,B = map(int,input().strip().split(' '))
	solMax,solMin = solveProblem(N,A,B)
	print("{} {}".format(solMax,solMin))


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

int main(){
  int N;
  cin >> N;
  int64_t ans=0;
  int count=0;
  int n=N;
  while(n>0){
    count++;
    n/=10;
  }
  if(count%2==0){
    for(int i=0;i<count;i+=2){
      ans+=9*pow(10,i);
    }
  }else{
    for(int i=0;i<count;i+=2){
      ans+=9*pow(10,i);
    }
    ans-=pow(10,count)-1-N;
  }
  cout << ans <<endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
b = list(map(int,input().split()))
c=0

if n == 2:
    print(b[0]*2)
elif n==3:
    print(b[1]+min(b[0],b[1])*2)
else:
    co = [min(x , y) for (x, y) in zip(b[0:-1], b[1:])]
    print(sum(co)+b[-1]+b[0])


Measured memory_bytes: 3064
import java.util.Scanner;

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

    // "Atcoder"は固定なので捨て
    scanner.next();

    // 二単語目を取得
    String word = scanner.next();

    // 単語の頭文字を取得
    String head = word.split("")[0];

    // "A" + head + "C" を出力
    System.out.println("A" + head + "C");
  }
}

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

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

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

	string ans = "Yes";

	for (int i = 1; i <= n; i++) {
		
		int tmp_d = abs(a[i] - a[i - 1]) + abs(b[i] - b[i - 1]);
		int tmp_t = t[i] - t[i - 1];

		if (tmp_t < tmp_d) {
			ans = "No";
			break;
		}
		else {
			if (tmp_t % 2 != tmp_d % 2) {
				ans = "No";
				break;
			}		
		}

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

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
const int maxn=1e6+5;
int x,y;
int f[maxn];
int invf[maxn];
inline int ksm(int x,int y){
	if(!y) return 1;
	if(y==1) return x;
	int tmp=ksm(x,y/2);
	tmp=(1ll*tmp*tmp)%MOD;
	if(y&1) return (1ll*tmp*x)%MOD;
	else return tmp;
}
inline int C(int x,int y){
	return 1ll*f[y]*invf[x]%MOD*invf[y-x]%MOD;
}
int main(){
	f[0]=invf[0]=1;
	for(int i=1;i<maxn;i++) f[i]=(1ll*f[i-1]*i)%MOD;
	invf[maxn-1]=ksm(f[maxn-1],MOD-2);
	for(int i=maxn-2;i>=1;i--) invf[i]=(1ll*invf[i+1]*(i+1))%MOD; 
	scanf("%d%d",&x,&y);
	int a=0,b=0;// a+2b=x; 2a+b=y;
	int tmp=(x+y)/3;
	if(tmp*3!=x+y){
		printf("0\n");
		return 0;
	}
	b=x-tmp;
	a=y-tmp;
	fprintf(stderr,"a = %d, b = %d\n",a,b);
	if(a<0||b<0){
		printf("0\n");
		return 0;
	}
	printf("%d\n",C(a,a+b));
	return 0;
}

Measured memory_bytes: 8192
from itertools import product

N = int(input())
A = []
XY = []
for _ in range(N):
  A.append(int(input()))
  XY.append([list(map(int, input().split())) for _ in range(A[-1])])

ans = 0
for C in product([0,1], repeat=N):
  if sum(C) <= ans:
    continue
  for i, c in enumerate(C):
    if c:
      for x, y in XY[i]:
        if C[x-1] != y:
          break
      else:
        continue
      break
  else:
    ans = max(ans, sum(C))

print(ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  vector<int> a(3);
  rep(i, 3) cin >> a[i];
  int ans = 1001001001;
  rep(i, 3) {
    for(int j = i+1; j<3; j++) {
      int tmp = a[i] + a[j];
      ans = min(tmp, ans);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#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 a,b,c,k; cin >> a >> b >> c >> k;
    ll ans = min(k,a);
    if(k - a - b > 0){
        ans -= k - a - b;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3612
#include<cstdio>
long long modpow(long long a,long long b,long long p)
{
    long long ret=1;
    for(;b>0;b>>=1,a=(a*a)%p)
        if(b&1)
            ret=(ret*a)%p;
    return ret;
}
long long phi(long long n)
{
    long long res=n,t=n;
    for(long long i=2;i*i<=t;i++)
        if(t%i==0)
        {
            res-=res/i;
            while(t%i==0)
                t/=i;
        }
    if(t>1)
        res-=res/t;
    return res;
}
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {x=1;y=0;return a;}
    long long g;
    g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
long long solve(long long A,long long M)
{
	if(M==1)
		return 1;
    /*if(M<=500)
    {
        long long s=A;
        for(long long i=1;;i++)
        {
            if(s==i%M)
                return i;
            s=(s*A)%M;
        }
    }*/
    long long pM,At,d,t,x,y;
    pM=phi(M);
    d=gcd(M,pM);
    t=solve(A,d);
    At=modpow(A,t,M);
    exgcd(M/d,pM/d,x,y);
    x=x*(((t-At)%pM+pM)%pM)/d;
    x=((x%(pM/d))+pM/d)%(pM/d)+pM/d;
    return x*M+At;
}
int main()
{
    int Q;
    long long A,M;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%lld%lld",&A,&M);
        printf("%lld\n",solve(A,M));
    }
    return 0;
}


Measured memory_bytes: 128
// 21:50
//
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <cmath>
#include <stack>

#define REP(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

int main(){
  int A, B;
  string S;
  cin >> A >> B;
  cin >> S;

  int len = S.length();
  for(int i = 0; i < A; i++){
    if(!(isdigit(S[i]))){
      cout << "No" << endl;
      return 0;
    }
  }
  for(int i = A+1; i < len; i++){
    if(!(isdigit(S[i]))){
      cout << "No" << endl;
      return 0;
    }
  }
  if(S[A] != '-') cout << "No" << endl;
  else cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
import heapq
def main(): 
    x, y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    pq = []
    heapq.heapify(pq)
    p.sort()
    q.sort()
    for i in range(x):
        heapq.heappush(pq,-1*p[len(p) - 1 - i])
    for i in range(y):
        heapq.heappush(pq, -1*q[len(q) - 1 - i])
    for i in range(len(r)):
        heapq.heappush(pq, -1*r[i])
    ans = 0
    for i in range(x + y):
        ans += -1*heapq.heappop(pq)
    print(ans)

main()

Measured memory_bytes: 29028
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF INT_MAX
#define LLINF LLONG_MAX

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<lint> x(n);
    rep(i, n){
        cin >> x[i];
    }
    lint ans = 1e18;
    rep(i, n-k+1){
        ans = min(ans, x[i+k-1] - x[i] + min(abs(x[i+k-1]), abs(x[i])));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main()
{
   cin.tie(0);
   ios::sync_with_stdio(false);
   long long n, k;
   cin >> n >> k;
   vector<long long> vc;
   for (long long i = 0; i < n; i++)
   {
      long long x;
      cin >> x;
      vc.push_back(x);
   }
   sort(vc.rbegin(), vc.rend());
   // for (long long i = 0; i < n; i++)
   // {
   //    cout << vc[i] << endl;
   // }
   long long sum = 0;
   if (k == 0)
   {
      for (long long i = 0; i < n; i++)
      {
         sum += vc[i];
      }
      cout << sum << endl;
      return 0;
   }
   for (long long i = 0; i < n; i++)
   {
      if (i >= k)
      {
         sum += vc[i];
      }
   }
   cout << sum << endl;
}

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

  int main(){
    int x, a, b, sa, sb;
    cin >> x >> a >> b;
    sa = abs(x - a);
    sb = abs(x - b);
    if (sa < sb){
      cout << 'A' << endl;
    } else {
      cout << 'B' << endl;
    }
  }


Measured memory_bytes: 256
n,m,l = map(int,input().split())
A=[]
B=[]
for i in range(n): A.append(list(map(int,input().split())))
for j in range(m): B.append(list(map(int,input().split())))
for A_r in A:
    print(" ".join(map(str,[sum([x*y for x,y in zip(A_r,[B_r[k] for B_r in B])]) for k in range(l)])))


Measured memory_bytes: 6316
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define all(x) x.begin(), x.end()
#define mem(arr,x) memset(arr, x, sizeof arr)
#define db(arr) for(auto x : arr) cout << x << " "; cout << "\n";
using namespace std;

// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ll power(ll n,ll m){
	if(m==0) return 1;
	ll val=power(n,m/2);
	if(m%2==0) return (val*val); else return ((val*val)*n);
}

ll powermod(ll n,ll m,ll MOD){
	if(m==0) return 1;
	ll val=powermod(n,m/2,MOD);
	val %= MOD;
	if(m%2==0) return (val*val) % MOD; else return (((val*val) % MOD) * n) % MOD;
}

void solve(){
	int n;
	cin >> n;
	int arr[n];
	ll ans = 0;
	int mn = INT_MAX;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
		if(i){
			if(arr[i - 1] > arr[i]) {ans += (arr[i - 1] - arr[i]); arr[i] = arr[i - 1];}
		}
	}
	cout << ans << "\n";
}

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

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);	
	#endif

	int t = 1;
	// cin >> t;

	for(int i = 1; i <= t; i++){
		// cout << "Case #" << i << ": ";
		solve();
	}

	return 0;
}

Measured memory_bytes: 4392
#pragma GCC optimize("Ofast")
#include <stdio.h>
//#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

using namespace std;


int main() {

	long n, a[100000], amount = 0, minusmin = 1000000001;
	int evencount = 0;
	scanf("%ld", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%ld", &a[i]);
		if (a[i] < 0)++evencount;
	}
	if ((evencount & 1)) {//奇数=マイナスが一つは発生する
		for (int i = 0; i < n; ++i) {
			if (a[i] < 0)a[i] *= -1;
			minusmin = min(minusmin, a[i]);
			amount += a[i];
		}
		amount -= 2 * minusmin;
	}
	else {//上でない=全部正
		for (int i = 0; i < n; ++i) {
			if (a[i] < 0)a[i] *= -1;
			amount += a[i];
		}
	}

	printf("%ld", amount);
	return 0;
}

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

int main(){
    int n, i;
    int a, b, c, count = 0;
    cin >> n >> c >> b;
    for(i=2; i<n; i++){
        cin >> a;
        if((a < b && b < c) || (a > b && b > c)) count++;
        c = b;
        b = a;
    }
    cout << count;
    return 0;
}

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


int main(){
    long long int n, m, k;
    long long int i;
    long long int a[200010], b[200010];
    long long int ans = 0;
    a[0] = b[0] = 0;

    scanf("%lld %lld %lld", &n, &m, &k);
    for(i = 0; i < n; i++){
        scanf("%lld", &a[i + 1]);
    }
    for(i = 0; i < m; i++){
        scanf("%lld", &b[i + 1]);
    }

    for(i = 0; i < n; i++){
        a[i + 1] += a[i];
    }
    for(i = 0; i < m; i++){
        b[i + 1] += b[i];
    }

    for(i = 0; i <= n; i++){
        while(m >= 0 && a[i] + b[m] > k){
            m--;
        }
        if(m >= 0){
            if (ans < i + m){
                ans = i + m;
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 4820
import itertools

n, a, b, c = map(int, input().split())
l = tuple(sorted(int(input()) for _ in range(n)))

# kind=0: 使わない
# kind=1: aの材料とする
# kind=2: bの材料とする
# kind=3: cの材料とする
ans = float('inf')
for bit in range(4 ** n):
    kinds = []
    while bit > 0:
        kinds.append(bit % 4)
        bit = bit // 4
    while len(kinds) != n:
        kinds.append(0)
    
    sizes = [0, 0, 0, 0]
    counts = [0, 0, 0, 0]
    for i in range(n):
        sizes[kinds[i]] += l[i]
        counts[kinds[i]] += 1

    _, p, q, r = sizes
    _, s, t, u = counts

    if s == 0 or t == 0 or u == 0: continue
    cost = abs(p - a) + abs(q - b) + abs(r - c) + 10 * max(0, s - 1) + 10 * max(0, t - 1) + 10 * max(0, u - 1)
    ans = min(ans, cost)

print(ans)
 

Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct Edge{
    int to,cost;
};
struct data{
    int nowp,sumcost,tic;
    data(){}
    data(int _nowp,int _sumcost,int _tic){
        nowp=_nowp,sumcost=_sumcost,tic=_tic;
    }
    bool operator<(const data &a)const{
        return sumcost>a.sumcost;
    }
};
const int INF=100000000;
int main(){
    while(1){
        int c,n,m,s,g;
        vector<Edge> edge[102];
        scanf("%d %d %d %d %d",&c,&n,&m,&s,&g);
        if(c==0&&n==0&&m==0&&s==0&&g==0)
            break;
        for(int i=0;i<m;i++){
            int be,af,co;
            scanf("%d %d %d",&be,&af,&co);
            Edge a;
            a.to=af,a.cost=co;
            edge[be].push_back(a);
            a.to=be;
            edge[af].push_back(a);
        }
        int coslis[11][102];
        fill(coslis[0],coslis[0]+11*102,INF);
        priority_queue<data> que;
        que.push(data(s,0,c));
        while(!que.empty()){
            data nowrig=que.top(); que.pop();
            //printf(" %d,%d,%d\n",nowrig.nowp,nowrig.sumcost,nowrig.tic);
            if(coslis[nowrig.tic][nowrig.nowp]!=INF)
                continue;
            coslis[nowrig.tic][nowrig.nowp]=nowrig.sumcost;
            for(int i=0;i<edge[nowrig.nowp].size();i++){
                data a;
                a.nowp=edge[nowrig.nowp][i].to;
                a.sumcost=nowrig.sumcost+edge[nowrig.nowp][i].cost;
                a.tic=nowrig.tic;
                que.push(a);
                if(0<nowrig.tic){
                    a.sumcost=nowrig.sumcost+(edge[nowrig.nowp][i].cost/2);
                    a.tic=nowrig.tic-1;
                    que.push(a);
                }
            }
        }
        int ans=INF;
        for(int i=0;i<=10;i++)
            ans=min(ans,coslis[i][g]);
        printf("%d\n",ans);
    }
    return 0;
}

Measured memory_bytes: 1348