akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <utility>
#include <functional>
#include <set>
#include <map>
#include <bitset>
#include <list>

using namespace std;


#define INF pow(10, 9)
// typedef priority_queue<tuple<int,int,int>, vector< tuple<int, int, int> >, greater< tuple<int, int, int> > > PQ;

typedef long long int ll;

ll calc_gcd(ll v1, ll v2)
{
    if(v1 < v2) swap(v1, v2);
    if(v2 ==0)
    {
        return v1;
    }
    else
    {
        return calc_gcd(v2, v1%v2);
    }

}

/*
def calc_lcm(value1:int, value2:int):
    gcd = calc_gcd(value1, value2)
    return value1 // gcd * value2

*/

ll  pow_mod(ll base, ll pow, ll div)
{
    ll res  = 1;
    while(pow >1)
    {
        if(pow & 1)
        {
            res = res*base % div;
        }
        base = base*base%div;
        pow /= 2;

    }

    return res *base%div;
}

void sieve(vector<int> &sieves, int num_max)
{
    for(int i=2; i<=num_max; i++)
    {
        int num = i;
        while(num <= num_max)
        {
            sieves[num] = min(sieves[num], i);
            num += i;
        }
    }

}

bool judge_and_add(vector<bool> &flag_sieve_not, vector<int> &sieves, int value)
{
    int v = value;
    int prime = 1;
    while(v>1)
    {
        if(flag_sieve_not[ sieves[v] ]==true && sieves[v] > prime) return false;
        flag_sieve_not[sieves[v]] = true;
        prime = sieves[v];
        v /= sieves[v];

    }
    return true;
}

int main(void)
{

    int N;
    cin >> N;
    vector<int> Array(N);

    int A_max=0;
    for(int i=0; i<N; i++)
    {
        cin >> Array[i];
        if(A_max < Array[i]) A_max = Array[i];
    }

    ll gcds = Array[0];
    bool flag_prime = true;

    vector<int> sieves(A_max+1, INF);
    sieve(sieves, A_max);

    vector<bool> flag_sieve_not(A_max+1);

    judge_and_add(flag_sieve_not, sieves, Array[0]);



    for(int i=0; i<N-1; i++)
    {
        gcds = calc_gcd(gcds, Array[i+1]);

        if(flag_prime ==true)
        {
            flag_prime = judge_and_add(flag_sieve_not, sieves, Array[i+1]);
        }

    }

    if(flag_prime ==true)
    {
        cout << "pairwise coprime" << endl;
    }
    else if(gcds > 1)
    {
        cout << "not coprime" << endl;
    }
    else
    {
        cout << "setwise coprime" << endl;
    }








    return 0;
}


Measured memory_bytes: 11060
/*
 * “My code isn't a mess! It's organised chaos!”
 */

/*
 * short     2^15-1 ~ 3e4
 * int       2^31-1 ~ 2e9
 * long x86  2^31-1 ~ 2e9
 * long long 2^63-1 ~ 9e18
 */

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define fr(a,b) for (int a=0; a<b; ++a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007ll;
const int infty = numeric_limits<int>::max();
struct _{_(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_;
void err() {cerr << endl;}
template<typename T, typename... Ts>
void err(T a, Ts... as) {cerr << a << ' '; err(as...);}

 /*
  * Всегда прогоняй макс-тест перед 
  * нажатием «Отослать». Всегда.
  */

bool check(string &s, string &kind) {
    int n = kind.size();
    for (int i = 2; i < n; ++i) {
        if (s[i-1] == 'o' && kind[i-1] == 'S' && kind[i-2] == 'S' ||
            s[i-1] == 'x' && kind[i-1] == 'S' && kind[i-2] == 'W' ||
            s[i-1] == 'o' && kind[i-1] == 'W' && kind[i-2] == 'W' ||
            s[i-1] == 'x' && kind[i-1] == 'W' && kind[i-2] == 'S') {
            kind[i] = 'S';
        } else {
            kind[i] = 'W';
        }
    }
    return (s[0] == 'o' && kind[0] == 'S' && kind[1] == kind[n-1] ||
            s[0] == 'x' && kind[0] == 'S' && kind[1] != kind[n-1] ||
            s[0] == 'o' && kind[0] == 'W' && kind[1] != kind[n-1] ||
            s[0] == 'x' && kind[0] == 'W' && kind[1] == kind[n-1]) && 
           (s[n-1] == 'o' && kind[n-1] == 'S' && kind[0] == kind[n-2] ||
            s[n-1] == 'x' && kind[n-1] == 'S' && kind[0] != kind[n-2] ||
            s[n-1] == 'o' && kind[n-1] == 'W' && kind[0] != kind[n-2] ||
            s[n-1] == 'x' && kind[n-1] == 'W' && kind[0] == kind[n-2]); 
} 

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

    string kind(n, ' ');
    
    kind[0] = 'S'; kind[1] = 'S';
    if (check(s, kind)) {
        cout << kind << endl;
        return 0;
    }
    kind[0] = 'S'; kind[1] = 'W';
    if (check(s, kind)) {
        cout << kind << endl;
        return 0;
    }
    kind[0] = 'W'; kind[1] = 'S';
    if (check(s, kind)) {
        cout << kind << endl;
        return 0;
    }
    kind[0] = 'W'; kind[1] = 'W';
    if (check(s, kind)) {
        cout << kind << endl;
        return 0;
    }
    cout << -1 << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    int cnt = 0;
    rep(i, N) {
        if (S[i] == 'I') cnt++;
        else cnt--;
        ans = max(ans, cnt);
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
/* AtCoder Regular Contest 087 (D - FT Robot) https://arc087.contest.atcoder.jp/tasks/arc087_b
*
* If number of turns that the robot made so far is:
* even --> he is walking on the x-axis now.
* odd  --> he is walking on the y-axis now.
*
* create dpx to know if it's possible to reach the required X-position.
* create dpy to know if it's possible to reach the required Y-position.
* If both are achievable then the answer is "Yes" else the answer is "No".
*
*/

#include <bits/stdc++.h>
#define F first
#define S second
#define SZ size()

using namespace std;
typedef long long ll;

int in(){int a; scanf("%d", &a); return a;}
ll inll(){ll a; scanf("%lld", &a); return a;}

//--------------------------------------------------

const int MAX = 8e3 + 5;
const int INF = 0x3f3f3f3f;

string s;
int X, Y;
vector <int> xsteps, ysteps;


int memx[MAX][MAX];

bool dpx(int i, int curX) {

    if(i == xsteps.SZ) return curX == X;
    int &res = memx[i][curX];
    if(res != -1) return res;
    res = 0;
    res = dpx(i+1, curX + xsteps[i]) || dpx(i+1, curX - xsteps[i]);
    return res;
}

int memy[MAX][MAX];

bool dpy(int i, int curY) {

    if(i == ysteps.SZ) return curY == Y;
    int &res = memy[i][curY];
    if(res != -1) return res;
    res = 0;
    res = dpy(i+1, curY + ysteps[i]) || dpy(i+1, curY - ysteps[i]);
    return res;
}


int main(){

    memset(memx, -1, sizeof memx);
    memset(memy, -1, sizeof memy);

    cin >> s;
    s = s + 'T';

    X = in(), Y = in();

    int steps = 0;
    int turns = 0;
    int xstart = 0;

    for(int i=0; i<s.SZ; i++){

        if(s[i] == 'F') steps++;

        else {

            if(turns == 0) {
                xstart = steps;
            }

            else if(steps > 0) {
                if(turns % 2 == 0) xsteps.push_back(steps);
                else ysteps.push_back(steps);
            }

            turns++;
            steps = 0;
        }
    }

    if(dpx(0, xstart) && dpy(0, 0)) printf("Yes\n");
    else printf("No\n");

}


Measured memory_bytes: 500992
N, M = map(int, input().split())

# 約数列挙
divisor = []
for i in range(1, int(M ** 0.5) + 1):
    if M % i == 0:
        divisor.append(i)
        divisor.append(M // i)

ans = 0
for d in divisor:
    if M // d >= N:
        ans = max(ans, d)

print(ans)


Measured memory_bytes: 3188
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
int i,j,n;
int main()
{
char a[2][4],b[2][4];
for(i=1;i<=2;i++)
{
	for(j=1;j<=4;j++)
	{
	scanf("%c",&a[i][j]);
	}
}
b[1][1]=a[2][3];
b[1][2]=a[2][2];
b[1][3]=a[2][1];
b[2][1]=a[1][3];
b[2][2]=a[1][2];
b[2][3]=a[1][1];

if(a[1][1]==b[1][1]&&a[1][2]==b[1][2]&&a[1][3]==b[1][3]&&a[2][1]==b[2][1]&&a[2][2]==b[2][2]&&a[2][3]==b[2][3])
	printf("YES");
	else
		printf("NO");

	return 0;
}

Measured memory_bytes: 256
N = int(input())
from collections import defaultdict
flag = [0 for i in range(N)]
G = defaultdict(list)
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数

from collections import deque
dist = [-1]*N
que = deque([0])
dist[0] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)


al = [0, 0]
for d in dist:
    al[d%2] += 1
if sum(al) // al[0] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            ansl.append(numbers3.pop())
        else:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
elif sum(al) // al[1] >= 3:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            elif numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            ansl.append(numbers3.pop())
    for a in ansl:
        print(a)
else:
    numbers1 = [i for i in range(1, N + 1) if i % 3 == 1]
    numbers2 = [i for i in range(1, N + 1) if i % 3 == 2]
    numbers3 = [i for i in range(1, N + 1) if i % 3 == 0]
    ansl = []
    for d in dist:
        if d % 2 == 0:
            if numbers1:
                ansl.append(numbers1.pop())
            else:
                ansl.append(numbers3.pop())
        else:
            if numbers2:
                ansl.append(numbers2.pop())
            else:
                ansl.append(numbers3.pop())
    for a in ansl:
        print(a)


Measured memory_bytes: 72456
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int acs(const void *a, const void *b) { 
  return *(int*)a - *(int*)b;
} /* 1,2,3,4.. */
int des(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
} /* 8,7,6,5.. */
int cmp_char(const void *a, const void *b) { 
  return *(char*)a - *(char*)b;
} /* a,b,c,d.. */
int cmp_str(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
} /* aaa,aab.. */
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define rep(i, l, r) for (int i = l; i < r; i++)
#define MAX 100001
#define MOD 1000000007
#define INF 1000000009
typedef long long int lli;

int main(void) {
  lli n, a, b;
  scanf("%lld %lld %lld", &n, &a, &b);

  lli count = n / (a + b);
  lli rem = n % (a + b);
  lli ans = count * a + min(rem, a);
  printf("%lld\n", ans);
  return 0;
}


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

typedef long long ll;
typedef long double ld;

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

    int N, M;
    cin >> N >> M;

    vector<int> a(N);
    vector<int> b(N);

    vector<int> c(M);
    vector<int> d(M);

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

    for(int i = 0; i < M; i++) {
        cin >> c[i] >> d[i];
    }

    for(int i = 0; i < N; i++) {
        int ans = 1;
        int count = pow(10, 9);
        for(int j = 0; j < M; j++) {
            if(abs(a[i] - c[j]) + abs(b[i] - d[j]) < count) {
                count = abs(a[i] - c[j]) + abs(b[i] - d[j]);
                ans = j + 1;
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cstdint>
#include <numeric>
#define INF 1000000000
#define LLINF 2000000000000000
#define MOD 1000000007
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
#define int long long

int n,m;
vector<int> route[100001];
int stp[100001];
int cnt = 0;

void func(int i){
  LOOP(k,route[i].size()){
    int t = route[i][k];
    // cerr << i << "," << t << endl;
    if(!stp[t]){
      stp[t] = i;
      cnt++;
    }
  }
  LOOP(k,route[i].size()){
    int t = route[i][k];
    // cerr << i << "," << t << endl;
    if(stp[t] == i){
      func(t);
    }
  }
}

signed main(){
  priority_queue<P, vector<P>, greater<P> > q;
  int n,m;
  cin >> n >> m;
  LOOP(i,m){
    int a,b;
    cin >> a >> b;
    route[a].push_back(b);
    route[b].push_back(a);
  }
  q.push(P(0,1));

  while(!q.empty()){
    int sc = q.top().first;
    int i = q.top().second;
    // cerr << sc << "," << i << endl;
    q.pop();
    LOOP(k,route[i].size()){
      int t = route[i][k];
      // cerr << i << "," << t << endl;
      if(!stp[t]){
        stp[t] = i;
        q.push(P(sc+1,t));
        cnt++;
      }
    }
  }
  // func(1);
  // cerr << cnt << endl;
  if(cnt==n){
    cout << "Yes" << endl;
    LOOP(i,n-1){
      cout << stp[i+2] << endl;
    }
  }else{
    cout << "No" << endl;
  }
}


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

typedef long long lint;

const int MX=100010;

int n, A[MX], B[MX], C[MX];
lint ans;

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

	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>A[i]>>B[i], C[i]=A[i]+B[i], ans+=A[i];

	sort(C+1, C+n+1, greater<int>());

	for(int i=1; i<=n; i++){
		if(i%2==0) ans-=C[i];
	}

	cout<<ans<<'\n';


	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define ll long long 
#define vi vector<int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pb push_back
#define f(i,a,b) for(i=a;i<b;i++)
using namespace std;

int main()
{
int n,i,j,k=0,mx;

string s;
cin>>n>>s;


i=0,j=n-1;
while(i<j)
{
    if(s[i]=='W'&&s[j]=='R')
    {
        s[i]='R',s[j]='W',k++;
        i++,j--;
    }
    else if(s[i]=='W'&&s[j]=='W')j--;
    
    else if(s[i]=='R'&&s[j]=='R')i++;
    
    else if(s[i]=='R'&&s[j]=='W')i++,j--;
}
cout<<k;
}

Measured memory_bytes: 3708
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        long cnt = 0;
        List<Long> wCnt = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'W') {
                cnt++;
            }
            wCnt.add(cnt);
        }

        long ans = 0;
        long wmax = wCnt.get(s.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'B') {
                ans += wmax - wCnt.get(i);
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 34736
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

int main() {
	ll n, a, b;
	ll x, y, z;

	cin >> n >> a >> b;

	if (a < b) {
		if (n >= 2) {
			x = a + b + (n - 2) * a;
			y = a + b + (n - 2) * b;

			z = y - x + 1;
		}
		else {
			z = 0;
		}
	}
	else if (a == b) {
		z = 1;
	}
	else if (a > b) {
		z = 0;
	}

	cout << z << endl;
}

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

typedef long long ll;
//const int INF = 2e9;
//const ll INF = 9e18;
const ll MOD = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N);
    for (int i=0;i<N;i++) cin >> A[i];
    //内部転倒数を数える
    ll p = 0;
    for (int i=0;i<N-1;i++){
        for (int j=i+1;j<N;j++){
            if (A[i]>A[j]) {
                p++;
            }
        }
    }
    //外部転倒数を数える
    ll q=0;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (A[j] > A[i]){
                q++;
            }
        }
    }
    //ll ans = (K*p + K*(K-1)/2%MOD*q)%MOD;
    ll ans = ((K*p)%MOD + ((K*(K-1)/2)%MOD*q)%MOD)%MOD;
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define ll long long
//vector<int> g1;
//g1.push_back(i);

using namespace std;

int main()
{
	int n;
	cin >> n;
	int a[n];
	for (int i=0;i<n;i++)
	{
		cin >> a[i];
	}
	int count = 1;
	for (int i=0;i<n;i++)
	{
		if(count == a[i]) count++;
	} 
	count--;
	if(count==0) cout << -1;
	else cout << n-count;
	return 0;
}



Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

namespace debug
{
    public static partial class Program
    {
        public static void Main()
        {
            n = Console.ReadLine().ToLong();
            var dis = Console.ReadLine().ArrayLongs();
            var sorted = dis.OrderBy(xx => xx).ToArray();

            k = sorted[0];
            
            long ans = 0;
            long right = 0;
            for (int left = 0; left < n; left++)
            {
                // rightを進めたときに条件を満たす
                while (right < n && sorted[right] <= k)
                {
                    right++;             // rightを進める
                }

                if (right == n - right)
                {
                    ans += sorted[right] - sorted[right - 1];
                }

                // leftをインクリメントする準備
                if (right == left) right++;
                if (right < n)
                {
                    k = sorted[right];
                }
            }

            Console.WriteLine(ans);
        }
    }

    public static partial class Program
    {
        //テンプレここから
        public static long a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
        public static long GCD(long aaa, long bbb) => bbb == 0 ? aaa : GCD(bbb, aaa % bbb);
        public static long LCM(long aaa, long bbb) => aaa * bbb / GCD(aaa, bbb);
        public static long ToLong(this double ddd) => (long) ddd;
        public static long ToLong(this string str) => long.Parse(str);
        public static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
        public static long[] ArrayLongs(this string str, char opr = ' ') => str.Split(opr).ToLong();
        public static long Diff(long aaa, long bbb) => Math.Abs(Math.Max(aaa, bbb) - Math.Min(aaa, bbb));
        public static long Sign(this long iii) => Math.Sign(iii);
        public static bool IsEven(this long iii) => iii % 2 == 0;
        public static readonly int[] Dx = {0, -1, 0, 1};
        public static readonly int[] Dy = {-1, 0, 1, 0};
        public const int MOD = 1000000007;
        public const string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        public const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
        public static long ToLong(this char ccc) => ccc.ToString().ToLong();
        public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
        public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);
        public static string JoinToStr(this IEnumerable<long> array, string sep = "")
            => array.Select(xxx => xxx.ToString()).Join(sep);
        //テンプレここまで
    }
}

Measured memory_bytes: 26080
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int i,j,p,a,b,c,pp;
	int flg[60];
	scanf("%d %d %d",&a,&b,&c);
	for(i=0;i<60;i++)	flg[i]=0;
	p=0;
	while(1)	{
		pp=p%60;
		if(pp==c)	{
			break;
		}
		for(i=1;i<=a;i++)	{
			p++;
			pp=p%60;
			if(pp==c)	{
				break;
			}
		}
		if(pp==c)	break;
		if(flg[pp]==1)	{
			p=-1;
			break;
		}
		else	{
			flg[pp]=1;
		}
		p+=b;
	}
	printf("%d\n",p);	
	return 0;
}


Measured memory_bytes: 1028
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60


int main() {
    int N, M;
    cin >> N >> M;
    vector< vector<ll> > dist(N, vector<ll>(N, INF));
    REP(i, N) dist[i][i] = 0;
    REP(i, M) {
        int s, t;
        ll d;
        cin >> s >> t >> d;
        dist[s][t] = d;
    }

    
    REP(k, N)
        REP(i, N)
            REP(j, N)
                if(dist[i][j] > dist[i][k] + dist[k][j] && dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = dist[i][k] + dist[k][j];

    REP(i, N)
        if(dist[i][i] < 0) {
            cout << "NEGATIVE CYCLE" << endl;
            return 0;
        }

    REP(i, N) {
        REP(j, N) {
            if(j != 0) cout << " ";
            if(dist[i][j] == INF)
                cout << "INF";
            else
                cout << dist[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3224
#include<bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define INF (ll)1e18
#define pii pair<ll,ll>
#define mod 1000000007 //998244353
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fb(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define PI 3.141592653589793238
#define pq priority_queue<ll>
#define pqr priority_queue<ll,vector<ll>,greater<ll>()>
using namespace std;
ll pow_mod(ll a,ll b)
{
	ll res=1;
	while(b!=0)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
void solve()
{
    ll n,m;
    cin>>n>>m;
    
    string s[n];
    
    for(ll i=0;i<n;i++)
    cin>>s[i];
    
    ll row_r[n][m];
    
    ll row_l[n][m];
    
    ll col_r[n][m];
    
    ll col_l[n][m];
    
    ll row_left=-1;
    
    ll row_right=m;
    
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            
            if(s[i][j]=='#')
            row_left=j;
            
            row_l[i][j]=row_left;
        }
        
        row_left=-1;
        
        for(ll j=m-1;j>=0;j--){
            if(s[i][j]=='#')
            row_right=j;
            
            row_r[i][j]=row_right;
        }
        
        row_right=m;
    }
    
    
    ll col_left=-1;
    
    ll col_right=n;
    ll ans=0;
    
    
      for(ll j=0;j<m;j++){
        for(ll i=0;i<n;i++){
            
            if(s[i][j]=='#')
            col_left=i;
            
            col_l[i][j]=col_left;
        }
        
        col_left=-1;
        
        for(ll i=n-1;i>=0;i--){
            if(s[i][j]=='#')
            col_right=i;
            
            col_r[i][j]=col_right;
        }
        
        col_right=n;
    }
    
    ll mx=0;
    
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            
            if(s[i][j]=='.'){
                ll r= row_r[i][j]-row_l[i][j]+col_r[i][j]-col_l[i][j]-3;
                
               // cout<<row_l[i][j]<<" "<<row_r[i][j]<<" "<<col_l[i][j]<<" "<<col_r[i][j]<<endl;
                ans=max(ans,r);
            }
        }
    }
    
    cout<<ans<<endl;
}
int32_t main()
{    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     
//Start from Here.

  ll t;
  t=1;
 // cin>>t;
  while(t--)
  solve();
  
//Good Bye!
    return 0;
}

Measured memory_bytes: 132708
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

n = onem()
a = []
for i in range(n):
    a.append(onem())
a.sort()
bbb = a[n//2+(n%2):]
bbb.reverse()

bbbb = a[n//2:]

if len(bbb) >= 3:
    bbbb = [bbbb[0]] + bbbb[2:] + [bbbb[1]]


aaa = a[:n//2+(n%2)]
if len(aaa) >= 3:
    aaa = [aaa[-1]] + aaa[:-2] + [aaa[-2]]

aaaa = a[:n//2]

lll = []
llll = []

for i in range(n):
    if i % 2 == 0:
        lll.append(aaa[i//2])
        llll.append(bbbb[i//2])
    else:
        lll.append(bbb[i//2])
        llll.append(aaaa[i//2])
ans = 0
an = 0
for i in range(n):
    if i == 0:
        st = lll[0]
        stt = llll[0]
    else:
        ans += abs(lll[i] - st)
        st = lll[i]
        an += abs(llll[i] - stt)
        stt = llll[i]
print(max(ans,an))







Measured memory_bytes: 11640
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>
#include <unordered_set>
#include <deque>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

deque<char> q;
string s;
int main() {
	ll now = 0;
	cin >> s;
	REP(i, s.size())q.push_back(s[i]);
	ll n;
	cin >> n;
	REP(i, n) {
		ll t;
		cin >> t;
		if (t == 1)now = 1 - now;
		else {
			ll a;
			char b;
			cin >> a >> b;
			if (now == 0 and a == 1)q.push_front(b);
			if (now == 1 and a == 2)q.push_front(b);
			if (now == 1 and a == 1)q.push_back(b);
			if (now == 0 and a == 2)q.push_back(b);
		}
	}
	if (now == 0) {
		while (!q.empty()) {
			cout << q.front();
			q.pop_front();
		}
	}
	else {
		while (!q.empty()) {
			cout << q.back();
			q.pop_back();
		}
	}
	cout << endl;
}



Measured memory_bytes: 896
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll e=0,w=0;
    rep(i,n){
        if(s[i]=='E') e++;
        else w++;
    }

    ll ans = 1000000;

    ll en=0,wn=0;

    rep(i,n){
        ll tmp;
        if(s[i]=='E'){
            en++;
            tmp = wn + e - en;
        }else{
            tmp = wn + e - en;
            wn++;
        }
        ans = min(ans,tmp);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3852
n = int(input())
li = []
flg = 0
for i in range(1000000):
  if n==1:
    break
  if i==0 or i==1 or n%i!=0:
    continue
  j = i
  cnt = 0
  while(n%j==0):
    if flg==0:
      flg = 1
    n /= j
    cnt += 1
  li.append(cnt)
if flg==0 and n!=1:
  print(1)
elif flg==0 and n==1:
  print(0)
elif n==1:
  ans = 0
  for e in li:
    i = 1
    while(e-i>=0):
      e -= i
      i += 1
      ans += 1
  print(ans)
else:
  ans = 1
  for e in li:
    i = 1
    while(e-i>=0):
      e -= i
      i += 1
      ans += 1
  print(ans)

Measured memory_bytes: 9304
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  int w,h;
  cin>>w>>h;
  vector<vector<int> > s(h,vector<int>(w,0));
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      cin>>s[i][j];
  int a=0,b=0;
  vector<int> c[2];
  c[0]=c[1]=vector<int>(w,0);
  for(int i=0;i<h;i++){
    if(s[i][0]) a++;
    for(int j=0;j<w;j++)
      c[s[i][0]][j]+=s[i][j];
  }
  auto ng=[](){
    cout<<"no"<<endl;
    exit(0);
  };
  for(int j=0;j<w;j++){
    if(c[1][j]&&(c[1][j]!=a||c[0][j])) ng();
    if(c[0][j]&&(c[0][j]!=h-a||c[1][j])) ng();
    if(c[1][j]) b++;
  }
  int x=h-a,y=w-b,z=a*b+x*y;
  if(abs(a-x)>1||abs(b-y)>1||abs((h*w-z)-z)>1) ng();
  cout<<"yes"<<endl;
  return 0;
}

Measured memory_bytes: 7092
/*Name:- Prince Soni
College:- Jalpaiguri Government Engineering College*/
 
// this is how we declare a constant value
// const int xyz=2500000;
 
 
#include <bits/stdc++.h> 
using namespace std; 
 
#define ll long long int
#define fio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define fr(i,n) for(ll i=0;i<n;i++)
#define fr1(i,n) for(ll i=1;i<=n;i++)
#define endl "\n"
 
ll h[100005];
ll dp[100005];
 
 
int min_cost(ll n,ll k){
    if(n<=0)
      return 1e9;
    if(n==1)
    return dp[1]=0;
    
    if(dp[n]==-1)
    {
        dp[n]=1e9;ll y;
        for(int i=1;i<=k;i++)
        {
            y=abs(h[n]-h[n-i])+min_cost(n-i,k);
            dp[n]=min(y,dp[n]);
        }
    }
    return dp[n];
}
 
int main() 
{ 
    fio;
    ll n,k;
    cin>>n>>k;
    fr1(i,n)
    cin>>h[i];
    memset(dp, -1, sizeof dp);
    dp[1]=0;
    cout<<min_cost(n,k);
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
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;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n, m; cin >> n >> m;
    ll ans = 0;
    if (n > m/2) ans = m/2;
    else {
        m -= n*2;
        ans = n;
        ans += m/4;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))	

Measured memory_bytes: 14224
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;


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

  if (k <= 10){
    r += (100 * (10 - k));
  }
  cout << r << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int read(unsigned *N) {
	fscanf(stdin, "%d%d", N, N +1);
	if (*N + *(N +1) == 0) return 0;
	else return 1;
}

int main(void)
{
	unsigned No_s[2];
	
	while (read(No_s) != 0) 
	{
		if (*No_s <= *(No_s +1) )
			printf("%u %u\n", No_s[0], No_s[1]);
		else
			printf("%u %u\n", No_s[1], No_s[0]);
	}
	
	return 0;
}

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

int main()
{
    int n, ai, s = 0;
    vector<int> a, d;
    cin >> n;

    a.push_back(0);
    for(int i = 0; i < n; i++){
        cin >> ai;
        a.push_back(ai);
        d.push_back(abs(a[i + 1] - a[i]));
        s += d[i];
    }
    a.push_back(0);
    d.push_back(abs(a[n + 1] - a[n]));
    s += d[n];

    for(int i = 0; i < n; i++){
        cout << s - (d[i] + d[i + 1]) + abs(a[i + 2] - a[i]) << endl;
    }
    return 0;
}

Measured memory_bytes: 2164
#include "bits/stdc++.h"
#ifndef err
#define err(...)(void)0
#endif
using namespace std;
using ll = long long;
using ull = decltype(1ull);
template<class T>int size(T&&a) { return a.size(); }
#define REP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.first,_l##t=a.second;t<_l##t;t++)
#define RREP(t,a)for(typename make_signed<decltype(a.second)>::type t=a.second-1,_l##t=a.first;t>=_l##t;t--)
template<class B>pair<int, B>make_pair(B b) { return{ 0,b }; }
#define rep(t,...)REP(t,make_pair(__VA_ARGS__))
#define rrep(t,...)RREP(t,make_pair(__VA_ARGS__))
#define all(a)begin(a),end(a)
#define rall(a)a.rbegin(),a.rend()
#define var(t, ...) t __VA_ARGS__;in,__VA_ARGS__;

void Calc();
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin.exceptions(istream::failbit | istream::badbit);
  cout << fixed << setprecision(15); Calc(); cout.flush(); return 0;
}
template<class A>void amax(A&a, A b) { a = max(a, b); }
template<class A>void amin(A&a, A b) { a = min(a, b); }
template<class A>int comp(A a, A b) { return a < b ? 1 : b < a ? -1 : 0; }
struct Scanner {
  template<class A = string>A Next() { A a; cin >> a; return a; }
  template<class A = int>vector<A>Array(int n) { vector<A>a(n); for (A&i : a) cin >> i; return a; }
  string Line() const { string s; getline(cin, s); return s; }
  template<class A>Scanner&operator,(A&a) { a = Next<A>(); return *this; }
  template<class A>operator A() { return Next<A>(); }
}in;

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


void Calc() {

  var(int, n, m, X, Y);

  auto x = in.Array(n);
  auto y = in.Array(m);

  auto a = *max_element(all(x));
  auto b = *min_element(all(y));

  if (X < a && a < b &&  b <= Y) {
    err(X, a, b, Y);
    cout << ("No War") << endl;
  }
  else {
    cout << ("War") << endl;
  }
}


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

int main(){
  int h, w;
  cin >> h >> w;
  
  map<int,int> ns; //（現在地、スタート地点の最大値）
  multiset<int> dist; //現在地ースタート地点の最大値
  
  rep(i,w) ns[i] = i; //キーiにiを代入
  rep(i,w) dist.insert(0); //はじめは距離0
  
  rep(i,h){
    int a, b;
    cin >> a >> b;
    --a; --b;
    
    auto it = ns.lower_bound(a);
    int ms = -1; //最も右にある開始点を保持
    while(1){
      //壁を1だけ超えるスタート地点を取得（b+1）
      if(it == ns.end() || it -> first > b+1) break;
      ms = max(ms, it -> second);
      dist.erase(dist.find(it->first - it->second));
      ns.erase(it++);
    }
    //要素が見つからない、wを超えてしまう時を除く。
    if(ms != -1 && b+1 != w){
      dist.insert(b+1 - ms);
      ns[b+1] = ms; 
    }
    
    int ans = -1;
    if(dist.size() > 0){
      ans = *dist.begin();
      ans += i+1;
    }
    cout << ans << endl;
  }
    
  return 0;
}

Measured memory_bytes: 22312
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#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<ll,ll> P;
typedef pair<ll,ll> Pll;
//小数点以下　cout << fixed << setprecision(10) << num << endl;
//桁数はlog10(mid)でやれ　log(mid)/log(10)はWA
//long*long<0で判定するな
//開区間と閉区間
//アルファベットが何番目かは x=s[i]-'a'
//bfsはmain()内で　rep(i,h)rep(j,w)rep(i,4)でバグ
//切り上げ：(a+(b-1))/b
//32bit以上は 1ull<<j
// map 初期値0 for(auto itr=mp.begin();itr!=mp.end();++itr) itr->fi itr->se で全探索
// for(auto u:mp) u.fi u.se も可能
//n個のgcd,lcmは一つずつみて更新していく
//大きな数を扱うときは素因数分解した形で持っておく
// (l/a[i]) = l*powmod(a[i],MOD-2)%MOD;
//auto itr=lower_bound(ALL(a),key) a[itr-a.begin()]

int main(){
    ll h,w; cin >> h >> w;
    ll ans=1001001001;
    
    for(int i=1;i<h;i++){
        ll a=i*w; //１個
        //h-i,w
        if((h-i)%2==0||w%2==0){
            chmin(ans,abs(a-(h-i)*w/2));
        }else{
            ll b=(h-i)/2;
            chmin(ans,max(max(a,b*w),(h-i-b)*w)-min(min(a,b*w),(h-i-b)*w));
            ll c=w/2;
            chmin(ans,max(max(a,c*(h-i)),(w-c)*(h-i))-min(min(a,c*(h-i)),(w-c)*(h-i)));
        }
    }
    for(int i=1;i<w;i++){
        ll a=i*h;
        //h-i,w
        if((w-i)%2==0||h%2==0){
            chmin(ans,abs(a-(w-i)*h/2));
        }else{
            ll b=(w-i)/2;
            chmin(ans,max(max(a,b*h),(w-i-b)*h)-min(min(a,b*h),(w-i-b)*h));
            ll c=h/2;
            chmin(ans,max(max(a,c*(w-i)),(h-c)-(w-i))*min(min(a,c*(w-i)),(h-c)*(w-i)));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#square869120Contest#4_B
n,k=map(int,input().split())
a=list(map(int,input().split()))

ans=10**15
for i in range(2**n):
    if bin(i).count('1')<k:
        continue
    max_tmp=0
    res=0
    for j in range(n):
        if (i>>j)&1:
            if a[j]>max_tmp:
                max_tmp=a[j]
            else:
                res+=max_tmp-a[j]+1
                max_tmp+=1
        else:
            max_tmp=max(max_tmp,a[j])
    ans=min(res,ans)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int gcd(long long int a,long long int b) {
   long long int temp;
    while(b > 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main(){
 long long int n,k;
  cin>>n>>k;
  vector<long long int> v(n);
  for (int i=0;i<n;i++){
    cin>>v[i];
  }
  sort(v.begin(),v.end());
  long long int f=v[n-1];
  int result = v[0]; 
    for (int j = 1; j < n; j++) 
    {result = gcd(v[j], result);}
  long long int s=result;
  
  if (f<k){cout<<"IMPOSSIBLE"<<endl;}
  else if (k<=f && k%s==0){cout<<"POSSIBLE"<<endl;}
  else {cout<<"IMPOSSIBLE"<<endl;}
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    long long N, K;
    cin >> N >> K;
    long long ans = 0;
    
    for(long long k = K; k <= N + 1 ; k++){
        ans += N*k - k*k + k + 1;
        ans %= 1000000000 + 7;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  if A[i]<500000:
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  #if -A[i]+i>=0:
  	D[A[i]+i]+=1
  	E[-A[i]+i]+=1
   #print(E[-A[i]+i],-A[i]+i)

for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)

Measured memory_bytes: 35608
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath> 
#include <cctype>

using namespace std;

int main() {
    int N;
    cin >> N;
    int t[N], x[N], y[N];
    t[0] = x[0] = y[0] = 0;
    for (int i = 0; i < N; i++) {
        cin >> t[i + 1] >> x[i + 1] >> y[i + 1];
    }

    bool flag = true;
    for (int i = 0; i < N; i++) {
        int dt = t[i + 1] - t[i];
        int dist = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
        if (dist > dt) flag = false;
        if (dist % 2 != dt % 2) flag = false;
    }

    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1408
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int n = sc.NextInt();
        long d = sc.NextInt();
        long[] x = new long[n];
        long[] y = new long[n];
        for (int i = 0; i < n; i++)
        {
            x[i] = sc.NextInt();
            y[i] = sc.NextInt();
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            long d2 = x[i] * x[i] + y[i] * y[i];
            if (d2 <= d * d) ans++;
        }

        Console.WriteLine(ans);
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            if (_index >= _line.Length)
            {
                string s;
                do
                {
                    s = Console.ReadLine();
                } while (s.Length == 0);

                _line = s.Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public string ReadLine()
        {
            _index = _line.Length;
            return Console.ReadLine();
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            string s = Console.ReadLine();
            _line = s.Length == 0 ? new string[0] : s.Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 49292
w, h, n = map(int, input().split())
xl, xr = 0, w
yd, yu = 0, h
for i in range(n):
    x, y, a = map(int, input().split())
    if a == 1:
        if x < xl:
            continue
        elif xl <= x <= xr:
            xl = x
        else:
            xl, xr = 0, 0 # 抜けてた...
    elif a == 2:
        if xr < x:
            continue
        elif xl <= x <= xr:
            xr = x
        else:
            xl, xr = 0, 0
    elif a == 3:
        if y < yd:
            continue
        elif yd <= y <= yu:
            yd = y
        else:
            yd, yu = 0, 0
    elif a == 4:
        if y > yu:
            continue
        elif yd <= y <= yu:
            yu = y
        else:
            yd, yu = 0, 0

print((xr - xl) * (yu - yd))




Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

int main()
{
    int costo, vueltas, billete, aux;
    cin >> costo;
    aux = costo % 1000;
    billete = (costo / 1000) * 1000;
    if(aux > 0)
        billete += 1000;
    vueltas = billete - costo;
    cout << vueltas << endl;
}

Measured memory_bytes: 3584
from itertools import permutations
from math import sqrt

n = int(input())
position = [tuple(map(int,input().split())) for _ in range(n)]

def dist_calc(i,j):
  return sqrt(pow(position[i][0]-position[j][0],2)
              +pow(position[i][1]-position[j][1],2))

ans = 0
mean = 0
for tmp in permutations(range(n)):
  for j in range(n-1):
    ans += dist_calc(tmp[j],tmp[j+1])
  mean += 1
print(ans/mean) 

Measured memory_bytes: 9188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }




int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    
    string s;
    cin >> s;
    // 最低この数でないといけない, を更新する
    vector<int> a(sz(s) + 1);
    rep(i, sz(s)) {
        if (s[i] == '<') a[i + 1] = a[i] + 1;
    }
    for (int i = sz(s) - 1; i >= 0; --i) {
        if (s[i] == '>') chmax(a[i], a[i + 1] + 1);
    }
    ll ans = 0;
    rep(i, sz(s) + 1) ans += a[i];
    // rep(i, sz(s) + 1) cout << a[i] << " "; cout << endl;
    cout << ans << endl;
}



Measured memory_bytes: 2844
package main
import . "fmt"
import . "os"
func main() {
  var n int
  var s,t string
  set := make(map[string]struct{})
  Scan(&n)
  t = "shiritori"
  for i:=0;i<n;i++ {
    Scan(&s)
    if _,ng := set[s];ng {
      Println("No")
      Exit(0)
    }
    set[s] = struct{}{}
    if i > 0 && s[0:1] != t[len(t)-1:len(t)] {
      Println("No")
      Exit(0)
    }
    t = s
  }
  Println("Yes")
}

Measured memory_bytes: 512
(defun solve (n s)
  (multiple-value-bind (quotient remainder)
      (truncate n 2)
    (if (zerop remainder)
        (string= s s
                 :end1 quotient
                 :start2 quotient)
        nil)))

#-swank
(let* ((n (read))
       (s (read-line)))
  (format t "~:[No~;Yes~]~%" (solve n s)))


Measured memory_bytes: 12004
from functools import lru_cache
H, W, K = map(int, input().split())
mod = 1000000007
def amida(start, end):
    if end <= start:
        return 1
    if end > W-1:
        return 1
    return count(end-start+1)
@lru_cache(maxsize=None)
def count(n):
    res = 0
    if n <= 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    res += count(n-1)
    res += count(n-2)
    return res

dp = [[0 for j in range(W)] for i in range(H+1)]
dp[0][0] = 1

for i in range(1, H+1):
    for j in range(W):
        dp[i][j] += dp[i - 1][j] * (amida(0, j-1) * amida(j+1, W-1)) % mod
        if j > 0:
            dp[i][j] += dp[i - 1][j-1] * (amida(0, j-2) * amida(j+1, W-1)) % mod
        if j < W-1:
            dp[i][j] += dp[i - 1][j+1] * (amida(0, j-1) * amida(j+2, W-1)) % mod
print(dp[H][K-1]%mod)

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

int main(){
  int Q;
  cin >> Q;
  while(Q--){
    long long a, b;
    cin >> a >> b;
    long long m = sqrt(a*b);
    if(m*m == a*b){
      long long ans = (m-1)*2;
      if(a != m) --ans;
      cout << ans << endl;
    }else{
      long long ans = 2*m-1;
      if(m*(m+1) >= a*b) --ans;
      cout << ans << endl;
    }
  }
}


Measured memory_bytes: 256