akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
#define INF32 1'050'000'000
#define INF64 4'000'000'000'000'000'000
using ll = long long;
using namespace std;
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;
}

int gcd(int x, int y) {
    if (x < y)
        swap(x, y);
    if (y == 0)
        return x;
    else
        gcd(y, x % y);
}

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

    int A, B;
    cin >> A >> B;
    std::cout << gcd(A, B) << '\n';

    return 0;
}


Measured memory_bytes: 3172
n=int(input())
a=list(map(int,input().split()))
b=10**10
c=[b]*n
c[0]=0
c[1]=abs(a[1]-a[0])
for i in range(n-2):
    for j in range(1,3):
        c[i+j]=min(c[i+j],c[i]+abs(a[i+j]-a[i]))
c[-1]=min(c[-1],c[-2]+abs(a[-2]-a[-1]))
print(c[-1])

Measured memory_bytes: 13924
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n,k = mp()
p = lmp()
p = [p[i]-1 for i in range(n)]
c = lmp()


def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums

ans = -int(1e18)-5
for i in range(n):
    now = p[i]
    sc = [c[now]]
    cnt = 1
    while now != i:
        now = p[now]
        sc.append(c[now])
        cnt += 1
    cums = cum_sum(sc)[1:]
    if k <= len(cums):
        cums = cums[:k]
        ans = max(ans, max(cums))
    else:
        if cums[-1] <= 0:
            ans = max(ans, max(cums))
        else:
            lop = k // len(cums)
            u = [cums[j]+(lop-1)*cums[-1] for j in range(len(cums))] + [cums[j]+lop*cums[-1] for j in range(k%len(cums))]
            ans = max(ans,max(u))
print(ans)




Measured memory_bytes: 168592
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
#define MOD 1000000007

int main(){
    int r,c;
    cin >> r >> c;
    vector<vi> field(r,vi(c));
    rep(i,r) rep(j,c) cin >> field[i][j];

    vector<pair<int,int>> from,to;

    rep(i,r) rep(k,c){
        int j=k;
        if(i%2==1) j=c-1-k;
        if(field[i][j]%2==0) continue;

        //偶数行目の時の縦移動
        if(i%2==0&&j==c-1&&i<r-1){
            if(field[i][j]%2==1){
                from.push_back({i+1,j+1});
                to.push_back({i+1+1,j+1});
                field[i+1][j]++;
            }
            continue;
        }
        //奇数行目
        if(i%2==1&&j==0&&i<r-1){
            if(field[i][j]%2==1){
                from.push_back({i+1,j+1});
                to.push_back({i+1+1,j+1});
                field[i+1][j]++;
            }
            continue;
        }   
        //その他
        if(i%2==0&&j<c-1){
            from.push_back({i+1,j+1});
            to.push_back({i+1,j+1+1});
            field[i][j+1]++;
        }
        if(i%2==1&&j>0){
            from.push_back({i+1,j+1});
            to.push_back({i+1,j+1-1});
            field[i][j-1]++;
        }
    }
    cout << from.size() << endl;
    for(int i=0;i<from.size();i++){
        cout << from[i].first << " " << from[i].second << " " << to[i].first << " " << to[i].second << endl;
    }
}

Measured memory_bytes: 6356
#define rep(i, a, b) for(int i = a; i < b; i++)
#define rrep(i, a, b) for(int i = a; i <= b; i++)

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

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

    if (op == "+") cout << A+B << endl;
    else cout << A-B << endl;
}

Measured memory_bytes: 888
#include <iostream>
int main()
{
  int h, w;
  while (std::cin >> h >> w) {
    if (h == 0 && w == 0) break;
    for (int i = 0;i < h; i++) {
      for (int j = 0; j < w; j++) {
        if ((i + j) % 2 == 0) std::cout << '#';
        else                  std::cout << '.';
      }
      std::cout << std::endl;
    }
    std::cout << std::endl;
  }
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define mem(a,i) memset(a,i,sizeof(a))
const double pi=acos(-1);
const int maxn=1e5+5;
const int mod=998244353;
ll mp[maxn];
int main()
{
    int n;
    mem(mp,0);
    sint(n);
    int m=0;
    int flag=0;
    for(int i=1; i<=n; i++)
    {
        int a;
        sint(a);
        if(i==1&&a)
            flag=1;
        mp[a]++;
        m=max(m,a);
    }
    if(flag)
        printf("0");
    else if(mp[0]!=1)
        printf("0");
    else
    {

        if(m>1&&mp[1]==0)
        {
            printf("0");
        }
        else
        {
            ll sum=1;
            for(int i=2; i<=m; i++)
            {
                if(mp[i]==0)
                {
                    printf("0");
                    return 0;
                }
                ll a=mp[i-1];
                ll s=1;
                //cout<<mp[i]<<endl;
                for(int j=1; j<=mp[i]; j++)
                    s=s*a%mod;
                sum=sum*s%mod;
            }
            printf("%lld\n",sum%mod);
        }
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}



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

    ll n;
    cin>>n;
    while(n){
        if(n%10==7){
            cout << "Yes\n";
            return 0;
        }
        n/=10;
    }
    cout << "No\n";

}

Measured memory_bytes: 3652
#include <iostream>
#include <sstream>
#include <string>

#if defined SUBLIME
#  define ISTREAM ss
#else
#  define ISTREAM cin
#endif


using namespace std;
int main()
{
	#if defined SUBLIME
		string str = "5 14 80";
		stringstream ss;
		ss << str;
	#endif
	int a, b, c;
	int cnt = 0;
	ISTREAM >> a >> b >> c;
	for(int i = a; i <= b;i++)
	{
		if(c % i == 0){
			cnt++;
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 3040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;ll k;int n;
bool check(){
    for(int i=0;i<n-2;i++){
        if(s[i]!=s[i+1])return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>s>>k;
    n=s.length();
    if(check()){
        ll all = n*k;
        cout<<all/2<<endl;
    }else if(s[0]==s[n-1]){
        int l1=0,l2=0;
        int l=0;while (s[l]==s[0])l++,l1++;
        int r=n-1;while (s[r]==s[n-1])r--,l2++;
        int tmp=0;
        for(int i=l,j;i<=r;i=j){
            j=i;
            while (s[j]==s[i])j++;
            int len = j-i;
            tmp+=len/2;
        }
        ll ans = k*tmp+(k-1)*((l1+l2)/2)+l1/2+l2/2;
        cout<<ans<<endl;
    }else{
        int tmp=0;
        for(int l=0,r;l<n;l=r){
            r=l;
            while (s[r]==s[l])r++;
            int len=r-l;
            tmp+=len/2;
        }
        ll ans = k*tmp;
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Joy
 */

#include <bits/stdc++.h>

#define REP(i, N) for (ll i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define INF ll(1e9)
#define INFL ll(1e18)
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
int ctoi(char c) {return c - '0';}

class DStringFormation {
public:
	void solve(std::istream& in, std::ostream& out) {
	    string S;
	    in >> S;
	    int Q;
	    in >> Q;
        bool order = true;
        deque<char> que;
        REP(i, S.size()) que.push_back(S[i]);
        REP(i, Q) {
	        int T;
	        in >> T;
	        if (T == 1) {
	            order ^= true;
	        } else {
	            int F; char C;
	            in >> F >> C;
	            if ((F == 1) ^ order) {
	                que.push_back(C);
	            } else {
	                que.push_front(C);
	            }
	        }
	    }
	    ll size = que.size();
        if (order) {
            REP(i, size) {
                out << que.front();
                que.pop_front();
            }
        } else {
            REP(i, size) {
                out << que.back();
                que.pop_back();
            }
        }
	    out << '\n';
	}
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
	DStringFormation solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

public class Main {
    void run() {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] aArr = new int[n];
        int[] bArr = new int[n];
        int[] cArr = new int[n - 1];

        for (int i = 0; i < n; i++) {
            aArr[i] = sc.nextInt() - 1;
        }
        for (int i = 0; i < n; i++) {
            bArr[i] = sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            cArr[i] = sc.nextInt();
        }

        int sum = 0;
        sum += bArr[aArr[0]];
        for (int i = 1; i < n; i++) {
            sum += bArr[aArr[i]];
            boolean hoge = aArr[i - 1] + 1 == aArr[i];
            if (hoge) {
//                System.out.println(i + " x");
                sum += cArr[aArr[i] - 1];
            }
        }

        // write your code
        System.out.println(sum);
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }
}


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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int a, b;
  cin >> a >> b;
  cout << lcm(a,b) << endl;
  return 0;
}


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

int main () {
  int numbers_of_row,numbers_of_columns;
  cin >> numbers_of_row >> numbers_of_columns;
  int row[numbers_of_row][numbers_of_columns] = { 0 };
  for (int i=0;i<numbers_of_row;++i) {
    int sum_of_rows = 0;
  	for (int j=0;j<numbers_of_columns;++j) {
	  cin >> row[i][j];
      cout << row[i][j] << " ";
	  sum_of_rows = sum_of_rows + row[i][j];
	}
	cout << sum_of_rows << endl;
  }

  int sum_of_a_column = 0;
  int sum_of_last_row = 0;
  for (int j=0;j<numbers_of_columns;++j) {
    for (int i=0;i<numbers_of_row;++i) {
	sum_of_a_column = sum_of_a_column + row[i][j];
	}
	cout << sum_of_a_column << " ";
	sum_of_last_row = sum_of_last_row + sum_of_a_column;
	sum_of_a_column = 0;
  }
  cout << sum_of_last_row << endl;
  return 0;
}

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

#define MAX_N 200001
#define INF 0x3FFFFFFF

using namespace std;

struct interval {
  int l, r;
  int val;
};

bool operator<(const interval &a, const interval &b) {
  return a.val > b.val;
}

int a[MAX_N], idx[MAX_N], even[4 * MAX_N], odd[4 * MAX_N];

void initEven(int k = 0, int X = 0, int Y = MAX_N - 1) {
  if (X == Y) { even[k] = X & 1 ? INF : a[X]; return; }
  int M = (X + Y) / 2;
  initEven(2 * k + 1, X, M);
  initEven(2 * k + 2, M + 1, Y);
  even[k] = min(even[2 * k + 1], even[2 * k + 2]);
}

void initOdd(int k = 0, int X = 0, int Y = MAX_N - 1) {
  if (X == Y) { odd[k] = X & 1 ? a[X] : INF; return; }
  int M = (X + Y) / 2;
  initOdd(2 * k + 1, X, M);
  initOdd(2 * k + 2, M + 1, Y);
  odd[k] = min(odd[2 * k + 1], odd[2 * k + 2]);
}

int query(int *tree, int x, int y, int k = 0, int X = 0, int Y = MAX_N - 1) {
  if (x <= X && Y <= y) return tree[k];
  if (y < X || Y < x) return INF;
  int M = (X + Y) / 2;
  return min(query(tree, x, y, 2*k+1, X, M), query(tree, x, y, 2*k+2, M+1, Y));
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    idx[a[i]] = i;
  }
  initEven();
  initOdd();
  priority_queue<interval> pq;
  pq.push(interval {1, n, query(odd, 1, n - 1)});
  vector<int> result;
  while (!pq.empty()) {
    interval iv = pq.top();
    pq.pop();

    result.push_back(iv.val);
    int second;
    if (idx[iv.val] & 1) {
      second = query(even, idx[iv.val] + 1, iv.r);
    } else {
      second = query(odd, idx[iv.val] + 1, iv.r);
    }
    result.push_back(second);

    int l1 = iv.l;
    int r1 = idx[iv.val] - 1;
    if (l1 < r1) {
      if (l1 & 1) {
        pq.push(interval {l1, r1, query(odd, l1, r1 - 1)});
      } else {
        pq.push(interval {l1, r1, query(even, l1, r1 - 1)});
      }
    }

    int l2 = idx[iv.val] + 1;
    int r2 = idx[second] - 1;
    if (l2 < r2) {
      if (l2 & 1) {
        pq.push(interval {l2, r2, query(odd, l2, r2 - 1)});
      } else {
        pq.push(interval {l2, r2, query(even, l2, r2 - 1)});
      }
    }

    int l3 = idx[second] + 1;
    int r3 = iv.r;
    if (l3 < r3) {
      if (l3 & 1) {
        pq.push(interval {l3, r3, query(odd, l3, r3 - 1)});
      } else {
        pq.push(interval {l3, r3, query(even, l3, r3 - 1)});
      }
    }
  }
  for (int r : result) printf("%d ", r);
  printf("\n");
  return 0;
}


Measured memory_bytes: 10636
import collections

n = int(input())
a = list(map(int, input().split()))
li = collections.Counter(a)
key = set(li.keys())
flag = True
mod = (10**9)+7

if n % 2:
    num = set(list(range(0,n,2)))#n-1
    if len(key ^ num) != 0:
        flag = False

    for i in li:
        if i == 0 and li[i] != 1:
            flag = False

        elif i != 0 and li[i] != 2:
            flag = False

    if flag:
        print((2**((n-1)//2))%mod)
    else:
        print(0)
else:
    num = set(list(range(1,n,2)))
    if len(key ^ num) != 0:
        flag = False

    for i in li:
        if li[i] != 2:
            flag = False
    if flag:
        print((2**(n//2))%mod)
    else:
        print(0)

Measured memory_bytes: 19800
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
long long a[200005];
long long pre[200005];
long long last[200005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i<=n;i++){
			scanf("%lld",&a[i]);
	}
	long long sumpre=0,sumlast=0;
	for(int i = 1;i<n;i++){
		sumpre=sumpre+a[i];
		pre[i]=sumpre;
//		printf("%lld++\n",pre[i]);
	}
	for(int i = n,j=1;i>1,j<n;i--,j++){
		sumlast=sumlast+a[i];
		last[j]=sumlast;
//		printf("%lld+++\n",last[i]);
	}
	long long d=(1ll<<60);
	for(int i = 1;i<n;i++){
//		printf("%lld\n",pre[i]-last[i+1]);
		d=min(d,abs(pre[i]-last[n-i]));
	}
	printf("%lld\n",d);
}


Measured memory_bytes: 4992
#include <stdio.h>
int main(void){
    int n,x;
    while(1){
        scanf("%d %d",&n,&x);
        if(n==0 && x==0) break;
        int count=0;
        for(int i=1;i<=n-2;i++){
            for(int j=2;j<=n-1;j++){
                for(int k=3;k<=n;k++){
                    if(i<j && j<k)
                    if(i+j+k==x) count++;
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}



Measured memory_bytes: 2036
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using P = pair<int,int>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
const ll INF = 1LL<<60;




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

    int a;
    string ans;
    a = N%10;
    if(a == 2 ||a == 4 ||a == 5 ||a == 7 ||a == 9) ans = "hon";
    else if(a == 0 ||a == 1 ||a == 6 ||a == 8) ans = "pon";
    if(a == 3) ans = "bon";

    cout << ans << endl;

    return 0;
}
//Ctrl+Shift+Bでコンパイルと実行を行ってデバッグすること

Measured memory_bytes: 3628
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    var x = 0
    var ans = 0
    sc.next().forEach {
        when (it) {
            'I' -> x++
            'D' -> x--
        }
        ans = Math.max(ans, x)
    }
    println(ans)
}

Measured memory_bytes: 31388
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll > ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define sz(x) (ll)(x).size()
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<endl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<sz(a);zz++) cerr<<a[zz]<<" ";cerr<<endl
#define trii(x) cerr<<#x<<": ("<<x.F<<","<<x.S<<")\n";
#define trvii(a) cerr<<#a<<": ";for(ll zz=0;zz<sz(a);zz++) cerr<<"("<<a[zz].F<<","<<a[zz].S<<") ";cerr<<nl
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<"\n"
#define trsetii(s) cerr<<#s<<": ";for(auto &i:s) trii(i);
#define epsilon 0.000000001L
#define mod 1000000007ll
#define inf 9999999999999999ll
#define nl endl
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()
#define fast()  ios_base::sync_with_stdio(false);cin.tie(NULL)
#define modulo 998244353ll

pair <lf,lf> cord(ll len,lf angle)
{
    return mp(len*cos(angle),len*sin(angle));
}


lf min_angle(lf m)//returns angle in radians
{
    return 2*(M_PI)*(m/60);
}

lf hour_angle(lf h,lf m)
{
    lf move_h=2*(M_PI)*(h/12);
    lf move_m=(M_PI/6)*(m/60);
    return move_h+move_m;
}


int main()
{
    fast();
    ll a,b,h,m;
    cin>>a>>b>>h>>m;
    lf a_m=min_angle(m);
    lf a_h=hour_angle(h,m);

    pair <lf,lf> c1=cord(b,a_m);
    pair <lf,lf> c2=cord(a,a_h);


    lf ans=(c1.F-c2.F)*(c1.F-c2.F) + (c1.S-c2.S)*(c1.S-c2.S);
    ans=sqrtl(ans);
    printf("%.11Lf\n",ans);
}



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

MOD = 1000000007
fact = []

def main():
    init_fact(200000)
    n = int(input())
    a = list(map(int, input().split()))
    sa = sorted(a)
    for i in range(n):
        if sa[i] == sa[i + 1]:
            double = sa[i]
            break
    idouble = []
    for i in range(n + 1):
        if a[i] == double:
            idouble.append(i)
    l = idouble[0]
    r = n - idouble[1]
    for k in range(1, n + 2):
        res = combi(n + 1, k) - combi(l + r, k - 1)
        res %= MOD
        print(res)

def combi(n, k):
    if k > n:
        return 0
    elif k == n:
        return 1
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % MOD
    return (numera * inv(denomi)) % MOD

def init_fact(maxn):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % MOD)

def inv(n):
    return pow(n, MOD - 2)

def pow(n, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2)
        return (x * x) % MOD
    else:
        x = pow(n, p - 1)
        return (x * n) % MOD

if __name__ == "__main__":
    main()


Measured memory_bytes: 79436
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<deque>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef long long ll;
typedef pair<int,int> pint;
const ll mod= 1e9+7;
const int inf=1e9+7;
const ll  longinf = 1LL<<60;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
  int n;
  cin>>n;
  ll a[n];
  rep(i,n)cin>>a[i];
  ll ans=0;
  if(a[0]!=0){
    cout<<-1<<endl;
    return 0;
    }
  rep(i,n-1){
    if(a[i]>i){
      cout<<-1<<endl;
      return 0;
      }
    if(a[i+1]>a[i]+1){
      cout<<-1<<endl;
      return 0;
      }
    if(a[i+1]==a[i]+1)ans++;
    else ans+=a[i+1];
    }
  cout<<ans<<endl;
  return 0;
  }

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

int main() {
  int X, Y, N;
  cin >> X >> Y >> N;
  int xl = 0, xr = X;
  int yl = 0, yr = Y;
  for (int i = 0; i < N; i++) {
    int x, y, a;
    cin >> x >> y >> a;
    if (a == 1) xl = max(x,xl);
    if (a == 2) xr = min(x,xr);
    if (a == 3) yl = max(y,yl);
    if (a == 4) yr = min(y,yr);
  }
  cout << max(0,xr-xl) * max(0,yr-yl) << endl;
}

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

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

struct Food {
	int a, b, value;
	Food(int _a, int _b, int _value) {
		a = _a;
		b = _b;
		value = _value;
	}
	bool operator<(const Food& f) const {
		return value < f.value;
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	deque<Food> V;
	REP(i, N) {
		int a, b;
		cin >> a >> b;
		int value = a + b;
		V.push_back(Food(a,b,value));
	}
	so(V);
	bool takahashi = true;
	ll ans = 0;
	while (!V.empty()) {
		if (takahashi) {
			Food f = V.back();
			V.pop_back();
			ans += f.a;
			takahashi = false;
		}
		else {
			Food f = V.back();
			V.pop_back();
			ans -= f.b;
			takahashi = true;
		}
	}
	cout << ans << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>

#define MAX_N 100000

int N;
std::pair<int, int> p[MAX_N];

int main() {
    int res=0;
    std::cin >> N;
    
    for (int i=0; i<N; i++) std::cin >> p[i].first >> p[i].second;

    std::sort(p, p+N);
    res = p[0].first;

    for (int i=1; i<N; i++) {
        res += p[i].first - p[i-1].first;
    }
    res += p[N-1].second;

    std::cout << res << std::endl;
    return 0;
}


Measured memory_bytes: 1024
/*
 *  頭ついてない
 *  まるで食べられたアンパンマンみたい
 */

#include <cstdio>
#include <cmath>
#include <queue>
#include <utility>

using namespace std;

typedef pair<int, int> P;
#define INF 0x40000000

class Edge {
public:
    int from;
    int to;
    int len;
};

class Vertex {
public:
    vector<Edge*> children;
};

Vertex vs[3000];
Edge es[200000];
int n, m, k;
int to_mall[3000];
priority_queue<P, vector<P>, greater<P> > q;
int min_d;
float answer;

int main() {

   scanf(" %d %d %d", &n, &m, &k);
   for (int i=0; i<m; i++) {
       int a, b, l;

       scanf(" %d %d %d", &a, &b, &l);
       --a;
       --b;
       es[i*2].from = a;
       es[i*2].to = b;
       es[i*2].len = l;
       es[i*2+1].from = b;
       es[i*2+1].to = a;
       es[i*2+1].len = l;
       vs[a].children.push_back(&es[i*2]);
       vs[b].children.push_back(&es[i*2+1]);
   }

   fill(to_mall, to_mall+n, INF);
   for (int i=0; i<k; i++) {
       int s;

       scanf("%d", &s);
       --s;
       to_mall[s] = 0;
       q.push(make_pair(s, 0));
   }


   while (!q.empty()) {
       P p = q.top(); q.pop();
       int s = p.first;

       if (to_mall[s] < p.second) continue;
       for (int j=0; j < vs[s].children.size(); j++) {
           Edge *e = vs[s].children[j];
           if (to_mall[e->to] > to_mall[s] + e->len) {
               to_mall[e->to] = to_mall[s] + e->len;
               q.push(make_pair(e->to, to_mall[e->to]));
           }
       }
   }

   answer = 0;
   for (int i=0; i<m*2; i++) {
       int a = es[i].from;
       int b = es[i].to;
       int l = es[i].len;
       float d = (to_mall[a] + to_mall[b] + l) / 2.0;

       if (d > answer) {
           answer = d;
       }
   }

   printf("%d\n", (int)ceil(answer));
}

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

int main(){
	ll a,b,c;
	cin >>a>>b>>c;
	ll t =0,tmpt =0;
	set<ll> ts;
	bool f = true;
	/*while(f){
		rep(i,0,a){
			t += 1;
			if(t%60 >= c){
				if(t > 60){
					cout << t - t % 60 + c<<endl;
				}
				else{
					cout << c << endl;
			
				}
				f = false;
				break;
			}
		}
		if(!ts.insert(t % 60).second){
			cout << -1 << endl;
			break;
		}
		t += b;
	}*/
	while(1){
	bool f=0;
	t = c;
	while(a+b<t){
		t-=a+b;
	}
	if(t<=a){
		cout<<c<<endl;
		break;
	}
	else{
		if(!ts.insert(t).second){
			cout<<-1<<endl;
			break;
		}
	}
		c+=60;
	}
}

Measured memory_bytes: 3112
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int preT = 0;
    int preX = 0;
    int preY = 0;
    for (int i = 0; i < N; i++) {
      int t = sc.nextInt();
      int x = sc.nextInt();
      int y = sc.nextInt();
      
      int diffT = t - preT;
      int diffX = Math.abs(x - preX);
      int diffY = Math.abs(y - preY);
      
      if (diffX + diffY > diffT
          || (diffT-diffX-diffY)%2 == 1) {
        System.out.println("No");
        return;
      }
      
      preT = t;
      preX = x;
      preY = y;
    }
    
    System.out.println("Yes");
  }
}

Measured memory_bytes: 85508
#include <algorithm>
#include <cassert>
#include <set>
#include <iostream>
#include <vector>

using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)

#define sz(x) int((x).size())
#define eb(x...) emplace_back(x)
#define ff first
#define ss second

using ll = int64_t;
const ll inf = 2e18;

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, false;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return y->p <= x->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, -m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && y->p <= (--x)->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

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

	int n; ll c; cin >> n >> c;
	ll h[n]; rep(i, 0, n) cin >> h[i];
	LineContainer L; L.add(2 * h[0], h[0] * h[0]);
	ll t = 0;
	rep(j, 1, n) {
		t = c + h[j] * h[j] - L.query(h[j]);
		L.add(2 * h[j], t + h[j] * h[j]);
	}
	cout << t;
}

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

int main() {
  long long n,m,ans=0,t=0;
  cin>>n>>m;
  long long a[n+1];
  a[0]=0;
  for(int i=1;i<n+1;i++){
    long long k;
    cin>>k;
    a[i]=(a[i-1]+k)%m;
    if(a[i]==0)ans++;
  }
  sort(a,a+n+1);
  for(int i=1;i<n;i++){
    if(a[i]==a[i+1])t++;
    else {
      ans+=1LL*t*(t+1)/2;
      t=0;
    }
  }
    cout<<ans+1LL*t*(t+1)/2<<endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
    using namespace std;
    int main(){
      string s,t;
      cin>>s;
      cin>>t;
      int ans=0;
      if(s[0]==t[0])ans++;
      if(s[1]==t[1])ans++;
      if(s[2]==t[2])ans++;
      cout<<ans;
      return 0;
    }

Measured memory_bytes: 256
while True:
    a,op,b = input().split()
    a = int (a)
    b = int (b)
    
    if op == "+":
        print(a+b)
    elif op == "*":
        print(a*b)
    elif op == "-":
        print(a-b)
    elif op == "/":
        print(a//b)
    elif op == "?":
        break
    



Measured memory_bytes: 5596
from collections import deque

k = int(input())
d = deque([1,2,3,4,5,6,7,8,9])

for i in range(k):
    x = d.popleft()
    if x % 10 != 0:
        d.append(10 * x + x % 10 - 1)

    d.append(10 * x + x % 10)
    
    if x % 10 != 9:
        d.append(10 * x + x % 10 + 1)

print(x)

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

using namespace std;

int N;
int Seedling[101], Temp[100];


void solve() {
	int index;
	bool flag;

	for (int i = 0; i < N + 1; ++i) {
		index = 0;
		for (int j = 0; j < N + 1; ++j) {
			if (i == j) {
				continue;
			}
			Temp[index++] = Seedling[j];
		}

		flag = true;
		for (int k = 2; k < index; ++k) {
			if (Temp[1] - Temp[0] != Temp[k] - Temp[k - 1]) {
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << Seedling[i] << endl;
			return;
		}
	}
}

int main() {

	while (cin >> N, N) {
		memset(Seedling, 0, sizeof(Seedling));
		memset(Temp, 0, sizeof(Temp));
		for (int i = 0; i < N + 1; ++i) {
			cin >> Seedling[i];
		}
		solve();
	}
	
	return 0;
}



Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n;
  cin >> n;
  int tmp = n;
  vi ans;
  for (int d = 2; d * d <= tmp; d++) {
    while (tmp % d == 0) {
      ans.push_back(d);
      tmp /= d;
    }
  }
  if (tmp != 1)
    ans.push_back(tmp);
  cout << n << ": ";
  int m = ans.size();
  REP(i, m) { cout << ans[i] << (i == m - 1 ? "\n" : " "); }
  return 0;
}



Measured memory_bytes: 3156
n, m = map(int, input().split())
A = []
B = []
for i in range(n):
    A.append(input())
for i in range(m):
    B.append(input())
if m > n:
    print('No')
    exit(0)
for j in range(n - m + 1):
    for i in range(n - m + 1):
        flag = 0
        for k in range(m):
            if A[j + k][i: i + m] == B[k][:]:
                flag = 1
                continue
            flag = 0
            break
        if flag == 1:
            print('Yes')
            exit(0)
print('No')


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int a[maxn];
int n;
ll ans = 0ll;

int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
    gbtb;
    cin >> n;
    repd(i, 1, n)
    {
        cin >> a[i];
    }
//    ans=n;
    ll sum = 0ll;
    ll xo = 0ll;
    int l = 1;
    int r = 0;
    ll cnt = 0ll;
    while (1)
    {
        while (r < n && sum + a[r + 1] == (xo ^ a[r + 1]))
        {
            r++;
            sum += a[r];
            xo ^= a[r];
        }
        cnt = r - l + 1;
//        ans+=(cnt*(cnt+1))/2;
        ans += cnt;
        sum -= a[l];
        xo ^= a[l++];
        if (l == n + 1)
        {
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}



Measured memory_bytes: 1024
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()


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

	vector<int> P(N);
	rep(i, N)
		cin >> P[i];

	vector<int> Q(N, 0);
	Q[0] = 0;

	repl(i, 1, N)
	{
		int prev = i - 1;
		if (P[Q[prev]] >= P[i])
			Q[i] = i;
		else
			Q[i] = Q[prev];
	}

	int count = 0;
	rep(i, N)
	{
		if (Q[i] == i) count++;
	}


	cout << count << endl;

	return 0;
}

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

int main(){
	ll n;
	cin >> n;
	vector<ll> city(n+1);
	vector<ll> hero(n);
	ll num = 0;
	rep(i, n+1){
		cin >> city.at(i);
		num += city.at(i);
	}
	rep(i, n) cin >> hero.at(i);

	ll ans = 0;
	rep(i, n){
		if(city.at(i) <= hero.at(i)){
			hero.at(i)= hero.at(i) - city.at(i);
			city.at(i) = 0;
		}else{
			city.at(i) -= hero.at(i);
			hero.at(i) = 0;
		}

		if(0 < hero.at(i)){
			if(city.at(i+1) <= hero.at(i)) city.at(i+1) = 0;
			else city.at(i+1) -= hero.at(i);
		}
	}

	ll leave = 0;
	rep(i, n+1) leave += city.at(i);

	cout << num-leave << endl;
	return 0;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);

        int leftTop = sc.nextInt();
        int middleTop = sc.nextInt();
        int rightTop = sc.nextInt();
        int leftMiddle = sc.nextInt();
        int middleMiddle = sc.nextInt();
        int rightMiddle = sc.nextInt();
        int leftDown = sc.nextInt();
        int middleDown = sc.nextInt();
        int rightDown = sc.nextInt();

        String ans = "Yes";
        int[] aTop = {0, leftTop - middleTop, leftTop - rightTop};
        int[] aMiddle = {0, leftMiddle - middleMiddle, leftMiddle - rightMiddle};
        int[] aDown = {0, leftDown - middleDown, leftDown - rightDown};

        int[] bLeft = {0, leftTop - leftMiddle, leftTop - leftDown};
        int[] bMiddle = {0, middleTop - middleMiddle, middleTop - middleDown};
        int[] bRight = {0, rightTop - rightMiddle, rightTop - rightDown};

        if (!Arrays.equals(aTop, aMiddle) || !Arrays.equals(aTop, aDown)) {
            ans = "No";
        }

        if (!Arrays.equals(bLeft, bMiddle) || !Arrays.equals(bLeft, bRight)) {
            ans = "No";
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 23252
#include<iostream>
#include<cstdio>
#include<cstring>
#define E 100010
using namespace std;

char s[E],ss[E];

int main()
{
	scanf("%s",s);
	
	int len=strlen(s);
	for(int i=0;i<len;i++)ss[i]=s[len-i-1];
	for(int i=0;i<len;i++)
	{
		if(ss[i]=='b')
		{
			ss[i]='d';
			continue;
		}
		if(ss[i]=='d')
		{
			ss[i]='b';
			continue;
		}
		if(ss[i]=='p')
		{
			ss[i]='q';
			continue;
		}
		if(ss[i]=='q')
		{
			ss[i]='p';
			continue;
		}
	}
	
	for(int i=0;i<len;i++)
	{
		if(s[i]!=ss[i])
		{
			cout<<"No"<<endl;
			return 0;
		}
		else continue;
	}
	cout<<"Yes"<<endl;
	
	return 0;
}

Measured memory_bytes: 384
a,b,x = map(int,input().split())

import math 

if x>= a**2*b/2:
    tan = 2*(b/a-x/(a**3))
    y = math.atan(tan)
else :
    tan = a*(b**2)/(2*x)
    y = math.atan(tan)

print(math.degrees(y))

Measured memory_bytes: 9328
import Control.Applicative
import Control.Monad
import Data.List

main = do
    [n, a, b] <- fmap read . words <$> getLine :: IO [Int]
    ss <- getLine
    let f (p, q) s = do
            let pass = case s of
                    'a' -> p < a + b
                    'b' -> p < a + b && q < b
                    _   -> False
            let p' = if pass then p + 1 else p
            let q' = if s == 'b' then q + 1 else q
            if pass then putStrLn "Yes" else putStrLn "No"
            return (p', q')
    foldM_ f (0, 0) ss

Measured memory_bytes: 10876
#include<bits/stdc++.h>
#include<vector>
#define PAIR pair<int,int>
#define N 200005
#define LL long long
using namespace std;
const int mo=1e9+7,oo=1e9;
int n,m,X,Y,L[N],R[N],ans,fc[N],sz;
vector<int> A[N]; PAIR a[N];
LL fpm(LL x,LL y){ LL s=1; while(y){ if(y&1) s=(s*x)%mo; y>>=1,x=(x*x)%mo;} return s;}
int main()
{
	int i,c,w;
	scanf("%d %d %d",&n,&X,&Y);
	for(i=1;i<=n;i++){
		scanf("%d %d",&c,&w);
		A[c].push_back(w);
	  }
	for(i=1;i<=n;i++) sort(A[i].begin(),A[i].end());
	L[0]=R[n+1]=oo;
	for(i=1;i<=n;i++)
		if(!A[i].size()) L[i]=L[i-1];
		else L[i]=min(L[i-1],A[i][0]);
	for(i=n;i>=1;i--)
		if(!A[i].size()) R[i]=R[i+1];
		else R[i]=min(R[i+1],A[i][0]);
	for(i=1;i<=n;i++){
		while(A[i].size()){
			w=A[i][A[i].size()-1];
			if(w+min(L[i-1],R[i+1])<=Y||w+A[i][0]<=X) break;
			A[i].pop_back();
		  }
	  }
	for(i=1;i<=n;i++) if(A[i].size()) a[++m]=PAIR(A[i][0],A[i].size());
	sort(a+1,a+m+1),fc[0]=1;
	for(i=1;i<=n;i++) fc[i]=(1LL*fc[i-1]*i)%mo;
	for(i=1;i<=m;i++)
		if(a[i].first+a[1].first>Y) break;
	for(c=1;c<i;c++) sz+=a[c].second;
	ans=fc[sz];
	for(c=1;c<i;c++) ans=(1LL*ans*fpm(fc[a[c].second],mo-2))%mo;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 12544
#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>
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<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; }

int main() {
    ll n;
    cin >> n;
    cout << n * (n - 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static void Main () 
    {
        long n = long.Parse(Console.ReadLine().Split(' ')[0]);
        String[] line = Console.ReadLine().Split(' ');
        Dictionary<long, long> dic = new Dictionary<long, long>();
        long ans = 0;

        for (int i = 0; i < n; i++)
        {
            long val = long.Parse(line[i]);
            ans += val;

            if(dic.ContainsKey(val))
            {
                dic[val]++;
            }
            else
            {
                dic.Add(val, 1);
            }
        }

        n = long.Parse(Console.ReadLine().Split(' ')[0]);
        for (int i = 0; i < n; i++)
        {
            line = Console.ReadLine().Split(' ');
            long a = long.Parse(line[0]);
            long b = long.Parse(line[1]);

            if (dic.ContainsKey(a))
            {
                long inc = (b - a) * dic[a];
                ans += inc;
                if (dic.ContainsKey(b))
                {
                    dic[b] += dic[a];
                }
                else
                {
                    dic.Add(b,dic[a]);
                }
                dic[a] = 0;
            }

            Console.WriteLine(ans);
        }

    }
}

Measured memory_bytes: 54496
n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
temp=[]
i=0
for i in range(n):
  temp.append(t-h[i]*0.006)
x=[]
i=0
for i in range(n):
  x.append(abs(a-temp[i]))
ans=min(x)
print(x.index(ans)+1)


Measured memory_bytes: 3064
import java.io.*;
public class Main{
    public static void main(String args[]){
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int i=0;
        String[] line;
        line = new String[10000];
        try{
        while(i<10000){
            line[i] = reader.readLine();
            if(line[i].equals("0"))  break;
            i++;
        }
        i=0;
        while(i<10000){
            if(line[i].equals("0"))  break;
            System.out.println("Case "+(i+1)+": "+line[i]);
            i++;
        }
    }catch(IOException e){
        System.out.println(e);
    }catch(NumberFormatException e){
        System.out.println(e);
    }
    }
}


Measured memory_bytes: 31724
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<char> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};

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

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

//組み合わせを線形で
//参考:https://drken1215.hatenablog.com/entry/2018/06/08/210000

const int MXN=1000001;//変更可
ll fac[MXN],inv[MXN],finv[MXN];

void COMinit(int M) {
    fac[0]=fac[1]=1;
    inv[1]=1;
    finv[0]=finv[1]=1;
    for(int i=2;i<MXN;i++){
        fac[i]=fac[i-1]*i%M;
        inv[i]=M-M/i*inv[M%i]%M;
        finv[i]=finv[i-1]*inv[i]%M;
    }
}

ll COMBI(int N,int K,int M){
    if(N<K){
        return 0;
    }
    if(N<0||K<0){
        return 0;
    }
    return fac[N]*finv[N-K]%M*finv[K]%M;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    COMinit(MOD);
    int H,W,A,B;
    cin >> H >> W >> A >> B;
    ll ans=0;
    cerr << H-A+B-1 << endl;
    cerr << W+A-B-1 << endl;
    rep(i,H-A){
        //cout << i << endl;
        ans+=COMBI(H-A+B-1,i,MOD)*COMBI(W+A-B-1,H-i-1,MOD);
        ans%=MOD;
        //cout << H-i << endl;
        //cout << ans << endl;
    }
    cout << ans << endl;
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 27092
#pragma warning(disable:4996)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{

	int ii;
	char str[1201];

	//クリア
	memset(str, (int)0, sizeof(char) * 1201);

	fgets(str, 1200, stdin);

	for (ii = 0; ii < (int)strlen(str); ii++) {
		if ((str[ii] >= 'A' && str[ii] <= 'Z') || (str[ii] >= 'a' && str[ii] <= 'z')) {
			if (str[ii] & 0x20) {	//小文字
				str[ii] &= 0xdf;
			}
			else {	//大文字
				str[ii] |= 0x20;
			}
		}
	}

	printf("%s", str);

	getchar();

	return 0;

}

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


using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<string> &o) {
    string a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

typedef pair<ll, ll> P;

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


struct Q {
    ll a, b, c, d;
};

std::istream &operator>>(std::istream &in, Q &o) {
    cin >> o.a >> o.b >> o.c >> o.d;
    o.a--;
    o.b--;
    return in;
}

int check(vector<int> &v, vector<Q> &qs) {
    ll ans = 0;
    for (Q &q : qs) {
        if (v[q.b] - v[q.a] == q.c) ans += q.d;
    }
    return ans;
}

ll rec(vector<int> v, int n, int m, vector<Q> &qs) {
    ll ans = 0;
    if (v.size() == n) {
        ll now = check(v, qs);
        cmax(ans, now);
        return ans;
    }
    int start = v.empty() ? 1 : v.back();
    for (int i = start; i <= m; i++) {
        vector<int> u = v;
        u.push_back(i);
        ll now = rec(u, n, m, qs);
        cmax(ans, now);
    }
    return ans;
}

int main() {

    int n, m, q;
    cin >> n >> m >> q;
    vector<int> v;

    vector<Q> qs(q);
    rep(i, q) cin >> qs[i];

    ll ans = rec(v, n, m, qs);
    cout << ans << endl;

}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i));
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a); i>n; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
int n, k;
vi v;
inline int check(ll P) {
	int cnt = 0;
	rep(j, 0, k) {
		ll s = 0;
		while(s + v[cnt] <= P) {
			s += v[cnt];
			if(++cnt == n) return n;
		}
	}
	return cnt;
}
inline int f() {
	ll left = 0;
	ll right = n * *max_element(all(v));
	ll mid;
	while (right - left > 1) {
		mid = (left + right) / 2;
		int v = check(mid);
		if(v >= n) right = mid;
		else left = mid;
	}
	return right;
}
int main() {
	cin >> n >> k;
	v.resize(n); rep(i, 0, n) cin >> v[i];
	P(f());
	return 0;
}

Measured memory_bytes: 3296