akhauriyash/Code-Regression huggingface dataset:
import java.math.*;
import java.util.*;
  
  

public class Main {

	static int n,m,k,sx,sy,gx,gy,res;
	static char map[][];
	static class pair{
		int x,y;
		pair(int a,int b){
			this.x=a;
			this.y=b;
			
		}
	}
	static class edge{
		int x,y,sum;
		edge(int a,int b,int sum){
			this.x=a;
			this.y=b;
			this.sum=sum;
		}
	}
	static int d[][],dx[]= {-1,0,1,0},dy[]= {0,1,0,-1};
	static Vector<edge> find;
	static Comparator<edge> cmp=new Comparator<Main.edge>() {
		
		@Override
		public int compare(edge o1, edge o2) {
			
			return o1.sum-o2.sum;
		}
	};
	public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
        	n=scan.nextInt();
        	m=scan.nextInt();
        	k=scan.nextInt();
        	scan.nextLine();
        	find=new Vector<edge>();
        	map=new char[n][m];
        	d=new int[n][m];
        	for(int i=0;i<n;i++) {
        		String s=scan.nextLine();
        		for(int j=0;j<m;j++) {
        			map[i][j]=s.charAt(j);
        			if(map[i][j]=='S') {
        				sx=i;
        				sy=j;
        			}
        			if(map[i][j]>='1'&&map[i][j]<='9') {
        				find.add(new edge(i,j,map[i][j]));
        			}
        			
				}
        	}
        	Collections.sort(find,cmp);
        	gx=find.get(0).x;
        	gy=find.get(0).y;
        	res=0;
        	bfs();
        	System.out.println(res);
        	
        }
        
        
        
        
	}
	public static void bfs() {
		if(map[sx][sy]=='0'+k)return;
		Queue<pair> que=new LinkedList<Main.pair>();
		for(int i=0;i<n;i++)Arrays.fill(d[i], Integer.MAX_VALUE);
		que.add(new pair(sx,sy));
		d[sx][sy]=0;
		while(que.size()>0) {
			pair p=que.poll();
			if(p.x==gx&&p.y==gy)break;
			for(int i=0;i<4;i++) {
				int nx=p.x+dx[i],ny=p.y+dy[i];
				if(nx>=0&&nx<n&&ny>=0&&ny<m&&map[nx][ny]!='X'&&d[nx][ny]==Integer.MAX_VALUE) {
					que.add(new pair(nx,ny));
					d[nx][ny]=d[p.x][p.y]+1;
				}
			}
			
		}
		res+=d[gx][gy];
		sx=gx;
		sy=gy;
		que.clear();
		
		boolean flag=false;
		for(edge i:find) {
			if(flag) {
				gx=i.x;
				gy=i.y;
				break;
			}
			if(i.x==gx&&i.y==gy)flag=true;
			
		}
		bfs();
		
	}
	
	
	
	
	
}


Measured memory_bytes: 104032
import sys
readline=sys.stdin.readline

N=int(readline())

from collections import defaultdict
dic = defaultdict(int)

for i in range(N):
  dic[readline().rstrip()] += 1
  
print("AC x",dic["AC"])
print("WA x",dic["WA"])
print("TLE x",dic["TLE"])
print("RE x",dic["RE"])

Measured memory_bytes: 9476
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
ll p[100002];
ll find(ll x)
{
  return p[x]==x ? x : p[x]=find(p[x]);
}
int main()
{
  ll n,m,i;
  cin>>n>>m;
  ll link[m][2],sum[n],ans[m];
  for(i=0;i<n;i++)
  {
    p[i]=i;
    sum[i]=1;
  }
  for(i=0;i<m;i++)
  {
    cin>>link[i][0]>>link[i][1];
  }
  ans[m-1]=(n*(n-1)/2);
  for(i=m-1;i>=0;i--)
  {
    ll q,w;
    q=find(link[i][0]);
    w=find(link[i][1]);
    if(q!=w)
    {
      ans[i-1]=ans[i]-(sum[q]*sum[w]);
      sum[w]+=sum[q];
      p[q]=w;
    }
    else ans[i-1]=ans[i];
  }
  for(auto g: ans) cout<<g<<endl;
  return 0;
}


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

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

    string as, bs;
    for (int i = 0; i < b; i++) {
        as += to_string(a);
    }
    for (int i = 0; i < a; i++) {
        bs +=to_string(b);
    }
    if (as < bs) {
        cout << as << endl;
    }
    else {
        cout << bs << endl;
    }
}

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

using namespace std;
using ll = long long;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    ll n; cin >> n;
    
    ll res(0);
    
    if (n % 2)
        cout << 0;
    else
    {
        res += n / 10;
        n /= 10;
        while (n)
        {
             res += n / 5;
             n /= 5;
        }
        
        cout << res;
    }
}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> A(N), B(N);
  
  for (int i = 0; i < N; i++) cin >> A.at(i);
  
  int min_count = 0;
  
  int x0 = A.at(0);
  while (x0 % 2 == 0) {
    min_count++;
    x0 = x0 / 2;
  }
  
  for (int x : A) {
      int count = 0;
      while (x % 2 == 0) {
        count++;
        x = x / 2;
      }
    min_count = min (min_count, count);
  }
  
  cout << min_count << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>

#define _GLIBCXX_DEBUG
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    vector<char> v(9);
    for(int i=0; i<9; i++){
        cin >> v.at(i);
    }
    cout << v.at(0) << v.at(4) << v.at(8) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    string o,e;cin>>o>>e;
    reverse(o.begin(),o.end());
    reverse(e.begin(),e.end());
    string ans;
    int size = o.size()+e.size();
    for(int i=0;i<size;i++){
        if(i%2==1){ans.push_back(e.back());e.pop_back();}
        else{ans.push_back(o.back());o.pop_back();}
    }
    co(ans);
}

Measured memory_bytes: 256
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    
    L = ''
    R = ''
    c = 0
    for s in S:
        if s == '(':
            c += 1
        else:
            c -= 1

        if c < 0:
            L += '('
            c += 1

    R += ')' * c

    return L + S + R


if __name__ == '__main__':
    print(main())


Measured memory_bytes: 3060
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n").filter(Boolean);
    const n = +input[0];
  
    if (n <= 2) {
      console.log(1);
      return;
    }
  
    const xy = input.slice(1).map(s => s.split(' ').map(n => +n));
  
    const map = {};
    xy.forEach(a => {
      xy.forEach(b => {
        if (a === b) return; // 自分自身の場合
        
        const vec = [b[0] - a[0], b[1] - a[1]];
        const m = vec.join('_');
        map[m] = map[m] == null ? 1 : map[m] + 1;
      });
    });

	const res = Object.keys(map).reduce((r, xystr) => {
		const count = map[xystr];
        return count > r[0] ? [count, xystr] : [r[0], r[1]];
    }, [1, '']);
  	
//    const pq = res[1];
    
    console.log(n - res[0]);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 8652
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;


int main()
{
	double x1;
	double x2;
	double y1;
	double y2;
	
	cin >> x1 >> y1 >> x2>> y2;
	double d = sqrt((pow((x1 - x2), 2) + pow((y1 - y2), 2)));
	printf("%lf\n", d);


    return 0;
}

Measured memory_bytes: 3260
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,1};
const int dy[6] = {0, 1, 0, -1,1,-1};
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(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,K;
    cin >> N >> K;
    for(int i=0; i<K; i++){
        int a,b;
        cin >> a >> b;
        if(a > N/2) a = N+1-a;
        if(b > N/2) b = N+1-b;
        a--;b--;
        cout << min(a,b)%3+1 << enld;
    }
    return 0;
}


Measured memory_bytes: 3200
#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	char s[5003];
	scanf("%s", s);
	int i, j, k;
	int ans = 0;
	int count;
	for (i = 0; i <= n - 1 - ans; i++)
	{
		for (j = i + ans; j <= n - ans; j++)
		{
			count = 0;
			for (k = 0; i + k < j && j + k < n; k++)
			{
				if (s[i + k] == s[j + k])
					count++;
				else
					break;
			}
			if (ans < count)
				ans = count;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
typedef long long ll;
#include <bits/stdc++.h>

using namespace std;

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll n,a[3010];

int main() {
    std::cin >> n;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        ans += a[i]-1;
    }
    std::cout << ans << std::endl;
    
}


Measured memory_bytes: 256
import sys 
from collections import defaultdict
sys.setrecursionlimit(10**6)
MOD = 10**9+7 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
K = int(readline())
a = defaultdict(int)
cnt = 0
N = 7
while True:
    cnt += 1
    s = N % K
    if s == 0:
        print(cnt)
        sys.exit()
    if s in a:
        print(-1)
        sys.exit()
    a[s] = 1
    N += pow(10,cnt,K)*7 
    N %= K

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

using namespace std;
const int MOD = 1000000007,MAX = 510000;
long int pow107 = (int)pow(10, 9) + 7,llimit = LONG_MAX,fac[MAX], finv[MAX], inv[MAX];
int ilimit = INT_MAX;

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long int COM(long int n,long int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

bool comp(pair<int, int> a, pair<int, int> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

long int Func2(long int n,long int m){
    long int s2 = 1,
        r = 1;
    for(long int i = 1; i <= m; ++i){
        s2 = (s2*(n - (i - 1))/i) % (pow107);
    }
    return s2;
}

bool secsort(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second)return a.first > b.first;
    else return a.second > b.second;
}

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

long int LCM(long int a,long int b){
    return a/GCD(a,b)*b;
}

//long intの最大llimit
//intの最大ilimit
//10^9+7    pow107
//素数pn
//n乗jou
//階乗factorial
//コンビネーションFunc2
//コンビネーションCOMinit(),COM(n,m)

int main(){
    int n,a;
    cin >> n >> a;
    cout << n * n - a << endl;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
typedef pair<int,int>pii;
const int INF=100000000;
struct edge{
    int to,cost;
    edge(int a,int b){
        to=a;cost=b;
    }
    edge(){}
};
vector<vector<edge> >V;

int dijkstra(int s,int g){
    int d[100];
    fill(d,d+100,INF);
    d[s]=0;
    priority_queue<pii>Q;
    Q.push(pii(0,s));
    while(!Q.empty()){
        pii p=Q.top();Q.pop();
        int n=p.second,cost=p.first;
        if(d[n]<cost)continue;
        d[n]=cost;
        for(int i=0;i<V[n].size();i++){
            edge e=V[n][i];
            if(d[e.to]>d[n]+e.cost){
                Q.push(pii(d[n]+e.cost,e.to));
            }
        }
    }

    return d[g];
}
int main(){
    int n,m;
    cin>>n>>m;
    V.resize(n);
    for(int i=0;i<m;i++){
        int a,b,ab,ba;
        scanf("%d,%d,%d,%d",&a,&b,&ab,&ba);
        a--;b--;
        V[a].push_back(edge(b,ab));
        V[b].push_back(edge(a,ba));
    }
    int s,g,w,c;
    scanf("%d,%d,%d,%d",&s,&g,&w,&c);
    s--;g--;
    cout<<w-c-dijkstra(s,g)-dijkstra(g,s)<<endl;
    return 0;
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a,b,two=1,ans;
inline int log2(int k,int i=1){
	for(;i<k;i<<=1);
	return i;
}
signed main(){
	scanf("%lld%lld",&a,&b);
	if(a==b) return puts("1"),0;
	while(two<a) two<<=1;
	while(two>b){
		two>>=1;
		if(two&a) a-=two,b-=two;
	}ans=two-a;
	for(;two<=b;two<<=1) ans+=min(two-a+(int)log2(-two+min(2*two-1,b)+1),two);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */


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

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

int main(){
    ll n,m,ans;
    cin >> n >> m;
    if(n==m) cout << "Yes";
    else cout << "No";
    return 0;
}


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

namespace ABC084D {
    class Program {
        static void Main(string[] args) {
            bool[] primes = Enumerable.Repeat(true, 100001).ToArray();
            primes[0] = false;
            primes[1] = false;
            for (int i = 2; i < 100001; i++) {
                if (primes[i]) {
                    int num = i * 2;
                    while (num < 100001) {
                        primes[num] = false;
                        num += i;
                    }
                }
            }
            int[] like2017Nums = new int[100001];
            int likeNum = 0;
            for (int i = 0; i < 100001; i++) {
                if (primes[i] && primes[(i + 1) / 2]) {
                    likeNum++; //2は外れるので大丈夫
                }
                like2017Nums[i] = likeNum;
            }
            int Q = int.Parse(Console.ReadLine());
            for (int i = 0; i < Q; i++) {
                int[] input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
                int l = input[0];
                int r = input[1];
                Console.WriteLine(like2017Nums[r] - like2017Nums[l - 1]);
            }
        }
    }
}

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

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

    
    int n, x;
  cin >> n;
  vector<ll> arr(n+1);
  for(int i=1; i<n; i++){
    cin >> x;
    arr[x]++;
  }
  
  for(int i=1; i<=n; i++){
    cout << arr[i] << endl;
  }
    

    return 0;
}


Measured memory_bytes: 4764
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <math.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long> num;
    for(auto i=0; i<n; i++){
        long t;
        cin >> t;
        if (t == 0){
            cout << 0 << endl;
            return 0;
        }
        num.push_back(t);
    }
    long ans = 1;
    for(auto el : num){
        if (el <= 1000000000000000000 / ans){
            ans *= el;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

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

bool isPalindrome(string s) {
    int i=0, j=s.size()-1;
    while (i < j)
        if (s[i++] != s[j--]) return false;
    return true;
}

int main() {
    string s;
    cin >> s;
    if (isPalindrome(s) && isPalindrome(s.substr(0, s.size()/2)) && isPalindrome(s.substr(s.size()/2+1, s.size()/2)))
        cout << "Yes";
    else
        cout << "No";
}

Measured memory_bytes: 384
#include <stdio.h>
 
int Adj[101][101];
int d[101], f[101], color[101];
int n, time;
 
void DFS(void){
 
  int i;
 
  for(i = 1; i <= n ;i++){
    color[i] = 0;
  }
  time = 0;
 
  for(i = 1; i <= n; i++){
    if(color[i] == 0){
      DFS_Visit(i);
    }
  }
 
}
 
void DFS_Visit(int u){
 
  int i;
 
  color[u] = 1;
  time++;
  d[u] = time;
 
  for(i = 1; i <= n; i++){
    if( (Adj[u][i] == 1) && (color[i] == 0) ){
      DFS_Visit(i);
    }
  }
 
  color[u] = 2;
 
  f[u] = ++time;
 
}
 
main(){
  
  int i, j, m, l;
  
  scanf("%d", &n);
  
  for(i = 1; i <= n; i++){
    scanf("%d %d", &Adj[i][0], &m);
  
    for(j = 1; j <= n; j++){
      Adj[i][j] = 0;
    }
      
    for(j = 1; j <= m; j++){
      scanf("%d", &l);
      Adj[i][l] = 1;
    }
  
  }
  
  DFS();
 
  for(i = 1; i <= n; i++){
    printf("%d %d %d\n", i, d[i], f[i]);
  }
  
  return 0;
  
}

Measured memory_bytes: 636
// Nurbakyt Madibek
// Look at my code! IT'S AWESOME

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>

using namespace std;

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
#define sz(a) (int)((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pi;
typedef pair < ll, ll > pl;
typedef vector < pi > vi;
typedef vector < pi > vl;

const int inf = (int)1e9 + 123;
const ll infl = (ll)1e18 + 123;
const double eps = 1e-6;

const int MAX_N = (int)1e5 + 5;
const int mod = (int)1e9 + 7;

int n;
vector < pi > g[MAX_N];

int sz[MAX_N];

ll all;

vector < int > q;

void dfs(int v, int pr = -1) {
    sz[v] = 1;
    bool good = 1;
    for (auto to : g[v]) {
        if (to.f == pr)
            continue;
        dfs(to.f, v);
        all += 2ll * min(n - sz[to.f], sz[to.f]) * to.s;
        sz[v] += sz[to.f];
        if (sz[to.f] > n / 2)
            good = 0;
    }
    if (n - sz[v] > n / 2)
        good = 0;
    if (good)
        q.pb(v);
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d", &n);
    for (int i = 1, u, v, c; i < n; i++) {
        scanf("%d%d%d", &u, &v, &c);
        g[u].pb(mp(v, c)), g[v].pb(mp(u, c));
    }
    dfs(1);
    assert(sz(q) < 3 && sz(q) > 0);
    if (sz(q) == 2) {
        for (auto to : g[q[0]])
            if (to.f == q[1])
                all -= to.s;
    } else {
        int mini = inf;
        for (auto to : g[q[0]])
            mini = min(mini, to.s);
        all -= mini;
    }
    printf("%lld\n", all);
    return 0;
}


Measured memory_bytes: 12800
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    H = LI()
    ans = 0
    cnt_plus_height_minus_idx = defaultdict(int)
    cnt_minus_height_minus_idx = defaultdict(int)
    cnt_plus_height_plus_idx = defaultdict(int)
    cnt_minus_height_plus_idx = defaultdict(int)

    for idx in range(N):
        cnt_plus_height_minus_idx[H[idx] - idx] += 1
        cnt_minus_height_minus_idx[- H[idx] - idx] += 1
        cnt_plus_height_plus_idx[H[idx] + idx] += 1
        cnt_minus_height_plus_idx[- H[idx] + idx] += 1

    ans = 0

    for k, v in cnt_plus_height_minus_idx.items():
        if k in cnt_minus_height_minus_idx:
            ans += v * cnt_minus_height_minus_idx[k]

    # print(v)
    for k, v in cnt_plus_height_plus_idx.items():
        if k in cnt_minus_height_plus_idx:
            ans += v * cnt_minus_height_plus_idx[k]

    print(ans // 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 175972
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))
# N,K=10,5
# a=[5,-4,-5,-8,-4,7,2,-4,0,7]

b = []
w = []
riso = []

risonow = sum([a[i] for i in range(K) if a[i]>0])
riso.append(risonow)
bnow = sum([-a[i] for i in range(K) if a[i]<0])
b.append(bnow)

for i in range(K,N):
	if a[i]>0:
		risonow+=a[i]
	else:
		bnow+=-a[i]
	if a[i-K]>0:
		risonow-=a[i-K]
	else:
		bnow-=-a[i-K]
	riso.append(risonow)
	b.append(bnow)

riso.extend(b)
print(sum([i for i in a if i>0])-min(riso))


Measured memory_bytes: 14348
// AtCoder Beginner Contest 080 2017/12/03

#include <iostream>
using namespace std;

int ans = -(1 << 30);
using ushort = unsigned short;
// 自分の店を開くか
ushort my_shop = 0;
// 店の数
int n;
// ほかの店の開店時間
ushort others[110];
// ほかの店との兼ね合いによる利益
int profit[110][11];

void update(int n);
void calc_profit();
int pop_count(ushort a);
int pop_count(ushort a, ushort b);

int main(){
	// 店の数
	cin >> n;
	int input;
	// ほかの店の開店時間
	for(int j = 0; j < n; j++){
		others[j] = 0;
	for(int i = 0; i < 10; i++){
		cin >> input;
		others[j] |= (input << i);
	}
	}
	// 開店時間の重複数と利益
	for(int j = 0; j < n; j++){
	for(int i = 0; i < 11; i++){
		cin >> input;
		profit[j][i] = input;
	}
	}
	update(0);
	cout << ans << endl;
	return 0;
}

void update(int n){
	if(n == 10){
		// 店を一回も開かない場合ははじく
		if(my_shop == 0) return;
		calc_profit();
		return;
	}else{
		// この時間帯に店を開く場合
		my_shop |= (1 << n);  update(n + 1);
		// この時間帯に店を開かない場合
		my_shop &= ~(1 << n); update(n + 1);
	}
}

inline int max(int a, int p){
	return a < p? p: a;
}
void calc_profit(){
	int p = 0;
	for(int i = 0; i < n; i++){
		p += profit[i][pop_count(my_shop, others[i])];
	}
	ans = max(ans, p);
}

int pop_count(ushort a) {
	a = (a & 0x5555) + ((a >> 1) & 0x5555);// 0101 0101 0101 0101
	a = (a & 0x3333) + ((a >> 2) & 0x3333);// 0011 0011 0011 0011
	a = (a & 0x0f0f) + ((a >> 4) & 0x0f0f);// 0000 1111 0000 1111
	a = (a & 0x00ff) + ((a >> 8) & 0x00ff);// 0000 0000 1111 1111
	return a;
}
int pop_count(ushort a, ushort b) {
	return pop_count(a & b);
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n;
	int c[100];
	int v;
	int i, j;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%d", &c[i]);
	}
	
	for (i = 1; i < n; i++){
		for (j = 0; j < n; j++){
			printf("%d", c[j]);
			if (j < n - 1){
				printf(" ");
			}
		}
		printf("\n");
		v = c[i];
		j = i - 1;
		while (j >= 0 && c[j] > v){
			c[j + 1] = c[j];
			j--;
			c[j + 1]= v;
		}
	}
	
	for (i = 0; i < n; i++){
		printf("%d", c[i]);
		if (i < n - 1){
			printf(" ");
		}
	}
	printf("\n");
	return (0);
}

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

#define f(i) for(int i=0; i<10; ++i)


//0008
int main(){
	int x;

	while(cin >> x){
		int a,b,c,d;
		int count=0;

		f(a)f(b)f(c)f(d){
			if(a+b+c+d == x){
				++count;
			}
		}
		cout << count <<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>

#define MAX_NUM 21

int numbers[100];
long long values[100][MAX_NUM];

int main(int argc, char const* argv[])
{
    int len;

    std::cin >> len;
    for (int i = 0; i < len; i++) std::cin >> numbers[i];

    values[0][numbers[0]] = 1;
    for (int i = 1; i < len-1; i++) {
        for (int j = 0; j < MAX_NUM; j++) {
            int add_value = j + numbers[i];
            if (add_value <= 20) values[i][add_value] += values[i-1][j];

            int minus_value = j - numbers[i];
            if (minus_value >= 0) values[i][minus_value] += values[i-1][j];
        }
    }

    std::cout << values[len-2][numbers[len-1]] << std::endl;

    return 0;
}

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

using namespace std;

int main() {

	int x, a, b;

	cin >> x >> a >> b;

	int xa, xb;

	if (a < x) {
		xa = x - a;
	}
	else {
		xa = a - x;
	}
	if (b < x) {
		xb = x - b;
	}
	else {
		xb = b - x;
	}
	if (xb > xa) {
		cout << "A" << endl;
	}
	else {
		cout << "B" << endl;
	}
	}
	

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.nextLine();
        String T = sc.nextLine();
        int sLen = S.length();
        int tLen = T.length();
        char[] s = S.toCharArray();
        char[] t = T.toCharArray();
        java.lang.String res = "";
        for (int i = 0; i < sLen - tLen + 1; i++) {
            if (!check(s, t, i)) {
                continue;
            }
            StringBuilder builder = new StringBuilder();
            for (int j = 0; j < i; j++) {
                builder.append(s[j] == '?' ? 'a' : s[j]);
            }
            for (int j = i; j < i + tLen; j++) {
                builder.append(t[j - i]);
            }
            for (int j = i + tLen; j < sLen; j++) {
                builder.append(s[j] == '?' ? 'a' : s[j]);
            }
            String temp = builder.toString();
            res = temp;
        }
        if (res == "") System.out.println("UNRESTORABLE");
        else System.out.println(res);

    }
    private static boolean check(char[] s, char[] t, int index) {
        for (int i = index; i < index + t.length; i++) {
            if (s[i] == '?') {
                continue;
            }
            if (s[i] != t[i-index]) {
                return false;
            }
        }
        return true;
    }
}


Measured memory_bytes: 21844
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	var ti, xi, yi int
	var t [] int
	var x [] int
	var y [] int
	t = append(t,0)
	x = append(x,0)
	y = append(y,0)
	for i:=0 ; i<n; i++ {
	  fmt.Scanf("%d %d %d", &ti, &xi, &yi)
	  t = append(t,ti)
	  x = append(x,xi)
	  y = append(y,yi)
	}

	var dt,dx,dy int
	possible := true
	for i:=1; i<=n; i++ {
	  dt = t[i] - t[i-1]
	  dx = x[i] - x[i-1]
	  dy = y[i] - y[i-1]
	  if dt < (dx+dy) || (dt-(dx+dy))%2 == 1{
		possible = false
		break
	  }
	}
	if possible {
	  fmt.Println("Yes")
	} else {
	  fmt.Println("No")
	}
}


Measured memory_bytes: 7552
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, _s, n) for(int i = _s, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
using namespace std;

#define repi(itr, ds) for(auto itr = ds.begin(); itr != ds.end(); itr++)
// vector
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for(T &x : vec) is >> x;
  return is;
}
// pair
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
// vector
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "{";
  for(int i = 0; i < vec.size(); i++) {
    os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
  }
  os << "}\n   ";
  return os;
}
// map
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
  os << "{";
  repi(itr, map_var) {
    os << *itr;
    itr++;
    if(itr != map_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}
// set
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
  os << "{";
  repi(itr, set_var) {
    os << *itr;
    itr++;
    if(itr != set_var.end()) os << ", ";
    itr--;
  }
  os << "}";
  return os;
}

#define DUMPOUT cerr

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
  DUMPOUT << head;
  if(sizeof...(Tail) > 0) {
    DUMPOUT << ", ";
  }
  dump_func(std::move(tail)...);
}
#ifdef DEBUG_
#define DEB
#define dump(...)                                                             \
  DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                             \
          << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \
          << "    ",                                                          \
      dump_func(__VA_ARGS__)
#else
#define DEB if(false)
#define dump(...)
#endif

typedef long long int ll;
const int MOD = 1e9 + 7;
const int INF = 1e9;

int main() {
  int K, X;
  cin >> K >> X;
  int s = max(X - (K - 1), -1000000);
  int e = min(X + (K - 1), 1000000);

  REPS(i, s, e + 1) { cout << i << " "; }
  cout << endl;
}


Measured memory_bytes: 256
'''
Aは移動関数と同数：xとy方向に合計で3進んでいるから
Bは移動回数の内、(i+1,j+2)を選んだ回数：
1回でx方向には1進み、y方向には2進む
進み方は2通りしかないので、全体の内、1通りを選んだ回数を求めればOK
'''
X,Y=map(int,input().split())
if (X+Y)%3!=0:#まず、条件に合わないケースを除外
  print(0)
  exit()
A=int((X+Y)/3)
B=int((2*Y-X)/3)
if A<0 or B<0:
  print(0)
  exit()
MOD=10**9+7
def comb(n,k):#組合せを求める関数
  tmp=1
  for i in range(n-k+1,n+1):#分子：n*(n-1)*...*(n-k+1)
    tmp*=i
    tmp%=MOD
  for i in range(1,k+1):#分母：k!
    tmp*=pow(i,MOD-2,MOD)#分母なので逆元にする
    tmp%=MOD
  return tmp
ans = comb(A,B)#上記説明の通り。要は組み合わせの問題
print(ans%MOD)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int SIZEN = 100010;
int N,A,B;
int a[SIZEN],b[SIZEN];
bool cmp(const int &A,const int &B){return A > B;}
int main(){
	scanf("%d%d%d",&N,&A,&B);
	for(int i = 1;i <= N;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+N,cmp);
	long long l = 1,r = 1e9,mid,ans = 0;
	while(l <= r){
		mid = (l+r)>>1;
		long long x = mid*B;
		long long sum = 0;
		for(int i = 1;i <= N;i++){
			if(a[i]-x <= 0)continue;
			if((a[i]-x)%(A-B) == 0)sum += (a[i]-x)/(A-B);
			else sum += (a[i]-x)/(A-B)+1;
		}
		//printf("mid = %d,sum = %d\n",mid,sum);
		if(sum > mid)l = mid+1;
		else r = mid -1,ans = mid;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int main(void){
	char a,b;
	int tp[]={1,0,0},temp,i;
	while(scanf("%c,%c",&a,&b)!=EOF){
		temp=tp[a-'A'];tp[a-'A']=tp[b-'A'];
		tp[b-'A']=temp;
	}
	for(i=0;i<3;i++){
		if(tp[i]==1){
			printf("%c\n",i+'A');
			break;
		}
	}
	return 0;
}

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

int main(){
    int a, b, c;
    std::cin >> a >> b >> c;
    int n = 0;
    if(a == b){ n++; }
    if(a == c){ n++; }
    if(b == c){ n++; }
    
    if(n == 1){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
    int N,M;
    cin>>N>>M;
    vector<int> mo(N,0);
    REP(i,M){
        int a,b;
        cin>>a>>b;
        mo[a-1]++;
        mo[b-1]++;
    }
    REP(i,N)cout<<mo[i]<<endl;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

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

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

	int ans = 0;
	rep(i, n) {
		int count = 0;
		while (a[i] % 2 == 0) {
			count++;
			a[i] /= 2;
		}
		ans += count;
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0; i<n; i++)
typedef long long ll;

using namespace std;

int main(){
    int N;  cin >> N;
    vector<int> v(N);
    priority_queue<int> q1, q2;
    rep(i,N)    cin >> v[i];
    int a1, a2, tmp, cnt, ans1, ans2;
    a1 = v[0];
    a2 = v[1];
    for(int i=1; i<=int(sqrt(a1)); i++){
        if(a1%i == 0){
            q1.push(i);
            if(a1%(a1/i)==0)    q1.push(a1/i);
        }
    }
    for(int i=1; i<=int(sqrt(a2)); i++){
        if(a2%i == 0){
            q2.push(i);
            if(a2%(a2/i)==0)    q2.push(a2/i);
        }
    }
    ans1 = 0;
    ans2 = 0;
    while(!q1.empty()){
        tmp = q1.top();
        q1.pop();
        cnt = 0;
        rep(i,N){
            if(v[i]%tmp != 0)   cnt++;
        }
        if(cnt <= 1){
            ans1 = tmp;
            break;
        }
    }
    while(!q2.empty()){
        tmp = q2.top();
        q2.pop();
        cnt = 0;
        rep(i,N){
            if(v[i]%tmp != 0)   cnt++;
        }
        if(cnt <= 1){
            ans2 = tmp;
            break;
        }
    }
    cout << max(ans1,ans2);
}

Measured memory_bytes: 3852
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N = int(input())
A = list(map(int, input().split()))

import math

# 葉から調査し、範囲を求める
limits = [(A[-1], A[-1])]
# for i in reversed(range(0, len(A)-1)):
for i in reversed(range(0, N)):
    min_ = math.ceil(limits[-1][0] / 2)
    max_ = limits[-1][1]
    # print("min_ {} max_ {} leaf {}".format(min_, max_, A[i]))
    limits.append((min_ + A[i], max_ + A[i]))
# print("limits: {}".format(limits))
if limits[-1][0] != 1:
    print(-1)
    quit()

# 根からにする
limits.reverse()

# 根から制約に基づき最大値を計算する
tree = [1]
for i in range(1, N+1):
    nodes = min(2 * (tree[-1] - A[i-1]), limits[i][1])
    tree.append(nodes)
# print(limits)
# print(tree)

ans = sum(tree)
print(ans)

Measured memory_bytes: 31912
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
int st[200002], dr[200002], v[200002], n;
int main() {
    DAU
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> v[i];
    for (int i = 1; i <= n; ++i)
        st[i] = max(v[i-1], st[i-1]);
    for (int i = n; i >= 1; --i)
        dr[i] = max(v[i+1], dr[i+1]);
    for (int i = 1; i <= n; ++i)
        cout << max(st[i], dr[i]) << '\n';
    PLEC
}


Measured memory_bytes: 5972
from collections import deque
S = input()
Q = int(input())

state = 1 # 反転していたら-1
Stock = deque([S])
for i in range(Q):
    q = input()
    if q == '1':
        state *= -1
    else:
        Y, f, c = q.split()
        if (state == 1 and f == '1') or (state == -1 and f == '2'):
            Stock.appendleft(c)
        elif (state == 1 and f == '2') or (state == -1 and f == '1'):
            Stock.append(c)
S = ''.join(Stock)
if state == -1:
    S = S[::-1]
print(S)

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

bool all_same(string S){
	char prev = S[0];
  	for (const auto &s: S)
      if (prev != s) return false;
  	return true;
}

int cnt_front(string S){
    char prev = S[0];
    int i = 0;
  	for (i = 0; i < S.length(); i++)
      if (prev != S[i]) return i;
    return i;
}

int cnt_back(string S){
    reverse(S.begin(), S.end());
    return cnt_front(S);
}

int main(void){
    // Your code here!
    string S;
    int64_t k;
    cin >> S >> k;
  	
  	if (all_same(S)){
  		cout << S.size() * k / 2 << endl;
  		return 0;
	}
  
    int n = S.length();
    int64_t ans = 0;
    int cnt = 1;
    char prev = 'A';
    for (int i = 0; i < n; i++){
        if (prev == S[i])
            cnt++;
        else{
            ans += cnt / 2;
            cnt = 1;
        }
      	prev = S[i];
    }
    ans += cnt / 2;

    int c = S[0] == S[n - 1] and cnt_front(S) % 2 == 1 and cnt_back(S) % 2 == 1;
    
    cout << ans * k + c * (k - 1) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define ll long long int
#define pb push_back

int main() {
  int A[3];
  cin >> A[0] >> A[1] >> A[2];

  int f = 0, s = 0;
  for(int i: A){
    if(i == 5) f++;
    if(i == 7) s++;
  }

  if(f==2 && s==1) print("YES");
  else print("NO");
}


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

int main(){
  int x1,y1,x2,y2,x3,y3,x4,y4=0;
  cin >>x1>>y1>>x2>>y2;
  
  cout<<x2+y1-y2<<" "<<y2-x1+x2<<" "<<x2+y1-y2+x1-x2<<" "<<y2-x1+x2+y1-y2<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

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

    cout<<3*r*r<<endl;

	return 0; 
}


Measured memory_bytes: 256
using System;

namespace ConsoleApplication7
{
    class Program
    {
        static void Main(string[] args)
        {
           while(true)
           {

                string Date = Console.ReadLine();
                string[] date = Date.Split(' ');
                int H = int.Parse(date[0]);
                int W = int.Parse(date[1]);

                if (H == 0 && W == 0)       //H,W??±???0????????????
                {
                    break;
                }
                for(int i = 1; i <= H; i++)
                {
                    for (int n = 1; n < W; ++n)
                    {
                        Console.Write("#");
                    }
                    Console.WriteLine("#");
                }
                Console.WriteLine();
            }
        }
    }
}

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

int main()
{
    int n = 0;
    std::cin >> n;
    if(n % 2 != 0)
    {
        std::cout << "No" << std::endl;
        return 0;
    }
    
    std::string str;
    std::cin >> str;
    
    std::cout << (str.substr(0, n / 2) == str.substr(n / 2) ? "Yes" : "No") << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;
#define reverse(s) reverse(s.begin(),s.end())

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

    if(a%2==0||b%2==0){
        puts("No");
        return 0;
    }
    puts("Yes");

    return 0;
}

Measured memory_bytes: 3596
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

using namespace std;

vector<char> alphaBet;

void makeAlphaBet() {
	alphaBet.clear();
	for (int i = 0; i < 26; ++i) {
		alphaBet.push_back('a' + i);
	}
	for (int i = 0; i < 26; ++i) {
		alphaBet.push_back('A' + i);
	}
	for (int i = 0; i < 10; ++i) {
		alphaBet.push_back('0' + i);
	}
	// for (int i = 0; i < 5; ++i) {
	// 	alphaBet.push_back('0' + i);
	// }
}

vector<string> f;
const int L = 128;
int totalL = 0;
int queryN = 0;
int maxQueryN = 850;

int makeQuery(string s) {
	cout << "? " << s << endl;
	int ans;
	cin >> ans;
	queryN += 1; 
	// if (queryN >= maxQueryN) {
	// 	for (;;);
	// }
	return ans;
}

void makeDecision(string s) {
	cout << "! " << s << endl;
}

void initF() {
	makeAlphaBet();
	int n = alphaBet.size();
	f = vector<string>(n);
	for (int i = 0; i < n; ++i) {
		f[i] = "";
	}
	totalL = 0;
	for (int i = 0; i < n; ++i) {
		string query = "";
		for (int j = 0; j < L; ++j) {
			query.push_back(alphaBet[i]);
		}
		int ans = makeQuery(query);
		f[i] = "";
		if (ans < L) {
			for (int j = 0; j < L - ans; ++j) {
				f[i].push_back(alphaBet[i]);
			}
		}
		totalL += (L - ans);
	}
}

string combine(string a, string b) {
	// cout << "combine " << a << " " << b << endl;
	if (a.length() == 0) {
		return b;
	}
	if (b.length() == 0) {
		return a;
	}
	int curA = 0, curB = 0;
	string res = "", tmp;
	int aL = a.length(), bL = b.length();
	while (curA < aL || curB < bL) {
		if (curA >= aL) {
			res.push_back(b[curB++]);
			continue;
		}
		if (curB >= bL) {
			res.push_back(a[curA++]);
			continue;
		}
		tmp = res + a[curA]; // + b.substr(curB);
		// tmp.push_back(a[curA]);
		// res.push_back(b[curB]);
		tmp += b.substr(curB);
		// for (int i = curB; i < bL; ++i) {
		// 	tmp.push_back(b[curB]);
		// }
		int ans = makeQuery(tmp);
		if (ans + (int)(tmp.size()) == totalL) {
			res.push_back(a[curA++]);
			continue;
		} else {
			res.push_back(b[curB++]);
			continue;
		}
	}
	return res;
}

string getF(int l, int r) {
	if (l == r) {
		return f[l];
	}
	int mid = (l + r) / 2;
	string left = getF(l, mid);
	string right = getF(mid + 1, r);
	return combine(left, right);
}

bool cmp(const string &a, const string &b) {
	return a.length() > b.length();
}

string combineF() {
	while (f.size() > 1) {
		sort(f.begin(), f.end(), cmp);
		if (f.back().empty()) {
			f.pop_back();
			continue;
		}
		int size = f.size();
		string a1 = f[size - 1];
		string a2 = f[size - 2];
		string a = combine(a1, a2);
		f.pop_back(); f.pop_back();
		f.push_back(a);
	}
	return f[0];
}

int main() {
	initF();
	// makeDecision(getF(0, alphaBet.size() - 1));
	// string res = combineF();
	string res = getF(0, alphaBet.size() - 1);
	cout << "! " << res << "\n";
	// cout << "! " << combineF() << endl;
	// return 0;
}

Measured memory_bytes: 3764
#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 bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

ll mod = 1000000007;

signed main()
{
    int l, r, d;
    cin >> l >> r >> d;
    cout << r / d - (l - 1) / d << endl;
    return 0;
}

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

int main()
{
	long long N, X, M;
	cin >> N >> X >> M;

	long long ans = 0;
	if( X == 0 ) {
		cout << ans << endl;
		return 0;
	}
	if( X == 1 ) {
		ans = N;
		cout << ans << endl;
		return 0;
	}
	long long A = X;
	long long a = -1;
	long long b = -1;
	long long sta;
	long long suma = X;
	long long sumb;
	set<long long> st;
	for( long long i = 1; i <= N; i++ ) {
		ans += A;
		A = A * A % M;
		if( a < 0 ) {
			if( st.count( A )  ) {
				a = i;
				sta = A;
				sumb = A;
			}
			else suma += A;
			st.insert( A );
		}
		else if( b < 0 ) {
			if( A == sta  ) {
				b = i;
				break;
			}
			else sumb += A;
		}
	}
	if( a < 0 || b < 0 ) {
		cout << ans << endl;
		return 0;
	}
	long long n = N - a;
	long long c = b - a;
	long long d = n / c;
	n = a + c * d + 1;
	ans = suma + sumb * d;
	A = sta;
	for( long long i = n; i <= N; i++ ) {
		ans += A;
		A = A * A % M;
	}
	cout << ans << endl;
}


Measured memory_bytes: 5896
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
  int n;
  int cse = 1;
  while(cin >> n, n){
    int ma[10][10]={{0}};
    int now = 1;
    int i,j,k;
    int cnt = now;
    for(k = 0 ; k < 2*n-1 ; k++ ){
      for( i = 0 ; i < n ; i++ ){
	if(k%2 == 1){
	  for( j = 0 ; j < n ; j++ ){
	    if(i + j == now-1){
	      ma[i][j]=cnt++; 
	    }
	  }
	} else {
	  for( j = 0 ; j < n ; j++ ){
	    if(2*(n-1)-(i + j) == now-1){
	      ma[n-1-i][n-1-j]=cnt++; 
	    }
	  }
	}
      }
      now++;
    }
    cout << "Case " << cse << ":" << endl;
    for(int i = 0 ; i < n ; i++ ){
      for(int j = 0 ; j < n ; j++ ){
	printf("%3d",ma[i][j]);
      }
      cout << endl;
    }
    cse++;
  }
}

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

int main(void) {
    int N, ans=0;
    cin >> N;

    if(N%2==0)
      ans = N/2;
    else
      ans = N/2 +1;

    cout << ans << endl;

    return 0;
}


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

int main() {
  int n,ans = 0;
  cin >> n;
  vector<int>h(n);
  for(int i = 0;i < n;i++){
    cin >> h.at(i);
  }
  ans += h.at(0);
  for(int i = 1;i < n;i++){
    if(h.at(i) > h.at(i-1)){
      ans += h.at(i)-h.at(i-1);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string> //文字列
#include <iomanip> //doubleの桁数指定 setprecision()
#include <list> //前後に数値を入れれる配列
#include <map> //map
#include <vector> //vecror



#define REP(i,m,n) for(ll i = (ll) (m);i < (ll) (n);i++) //forの短縮
#define rep(i,n) REP(i,0,n) //REPが0の時
#define ll long long int

using namespace std;

double PI = acos(-1); //円周率

//常設関数↓

//最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

//degree → radian
long double chg_DegRad(long double deg) {
	return deg * PI / 180.0;
}

//radian → degree
long double chg_RadDeg(long double rad) {
	return rad * 180.0 / PI;
}
 
//桁数
ll CountDigit(ll n) {
	ll digit = 1;
	while ((n /= 10) != 0) digit++;
	return digit;
}

//距離
double dis(double xa, double ya, double xb, double yb) {
	return pow(pow(xa - xb, 2.0) + pow(ya - yb, 2.0), 0.5);
}

//abs()平均
//pow(,)累乗


//提出コード↓

ll n, k, x;



int main() {
	cin >> n >> k;
	x = n % k;
	if (x <= k - x) cout << x << endl;
	else cout << k - x << endl;


	return 0;
}



Measured memory_bytes: 256
import sys
import numpy as np
from itertools import permutations as  P
from operator import itemgetter
from scipy.sparse.csgraph import floyd_warshall as wf

input = sys.stdin.readline

N, M, R = map(int, input().split())
r = list(map(int,input().split()))
edges = [list(map(int,input().split())) for _ in range(M)]
edges.sort(key=itemgetter(2),reverse=True)

G = np.full((N, N), np.inf)
for a, b, c in edges:
    G[a-1, b-1] = c
    G[b-1, a-1] = c
G = wf(G,directed=False)

def cost(G, path):
    ret = 0
    for i in range(len(path) - 1):
        ret += G[path[i] - 1, path[i + 1] - 1]
    return ret

ans = np.inf
for path in P(r):
    ans = min(ans, cost(G, path))

print(int(ans))


Measured memory_bytes: 19308
#!/usr/bin/env python3

import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    s, w = read_list(int)
    if s <= w:
        print("unsafe")
    else:
        print("safe")


if __name__ == "__main__":
    main()


Measured memory_bytes: 61720