akhauriyash/Code-Regression huggingface dataset:
n=int(input())
c,s,f=[],[],[]
for _ in range(n-1):
    x,y,z=map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

for i in range(n-1):
    temp=s[i]+c[i]
    for j in range(i+1,n-1):
        if temp<=s[j]: temp=s[j]+c[j]
        else:
            if (temp-s[j])%f[j]==0: temp+=c[j]
            else:
                k=(temp-s[j])//f[j]+1
                temp=s[j]+k*f[j]+c[j]
    print(temp)
print(0)

Measured memory_bytes: 9252
#include <iostream>
#include <algorithm>
using namespace std;
int p[105];
int m[110][110];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i-1];
        cin >> p[i];
        m[i][i] = 0;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = (i << 21);
            for (int k = i; k <= j - 1; k++) {
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
            }
        }
    }
    cout<<m[1][n]<<endl;
    return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> staff_num(N);
    for (int i = 0; i < N-1; i++)
    {
        int A;
        cin >> A;
        staff_num.at(A-1)++;
    }
    for (auto i: staff_num)
    {
        cout << i << endl;
    }
    return 0;
}

Measured memory_bytes: 4000
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

from pprint import pprint

def main():
    D, T, S = mis()
    if D<=T*S:
        print(Yes)
    else:
        print(No)





main()



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


signed main()
{
 
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   
 
 
#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif    


    int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int tot=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i%2)
        {
            if(tot+a[i]<=0)
            {
                ans+=abs(tot+a[i])+1;
                tot=1;
            }
            else
            {
                tot+=a[i];
            }            
        }
        else
        {
            if(tot+a[i]>=0)
            {
                ans+=tot+a[i]+1;
                tot=-1;
            }
            else
            {
                tot+=a[i];
            }            
        }        
    }

    int mn=ans;
    ans=0;
    tot=0;
    for(int i=1;i<=n;i++)
    {
        if(i%2==0)
        {
            if(tot+a[i]<=0)
            {
                ans+=abs(tot+a[i])+1;
                tot=1;
            }
            else
            {
                tot+=a[i];
            }            
        }
        else
        {
            if(tot+a[i]>=0)
            {
                ans+=tot+a[i]+1;
                tot=-1;
            }
            else
            {
                tot+=a[i];
            }            
        }        
    }
    mn=min(mn,ans);
    cout<<mn;

}

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

int main() {
    int N, s1, s2, s3;
    cin >> N;
    s1 = N/100;
    s2 = (N-s1*100)/10;
    s3 = N-s1*100-s2*10;
    cout << s1+s2+s3 << endl;
}

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

int main() {
  string N;
  cin >> N;
  
  bool flag = false;
  
  rep(i, N.size()){
  	if (N.at(i) == '7'){
    	flag = true;
    }
  }
  if (flag == true){
  	cout << "Yes" << endl;
  }
  else{
  	cout << "No" << endl;
  }
}

Measured memory_bytes: 3624
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  int S;
  if(N%2!=0) S = (N-1)*N/2;
  else S = (N-1)*N/2-1;
  vector<pair<int, int> > ans;
  map<int, int> amap;
  for(int i=1;i<=N;++i) amap[i] = S;
  int sum = N*(N+1)/2;
  int tmp;
  for(int i=N;i>0;--i) {
    sum -= i;
    tmp = sum - amap[i];
    for(int j=1;j<i;++j) {
      if(j==tmp) continue;
      ans.push_back(mp(i, j));
      amap[j] -= i;
    }
  }
  cout<<ans.size()<<endl;
  for(int i=0;i<ans.size();++i) {
    cout<<ans[i].fi<<" "<<ans[i].se<<endl;
  }
}



Measured memory_bytes: 3688
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <set>
#include<list>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e9
typedef long long ll;
using namespace std;

int main() {
    int x, y; cin >> x >> y;
    int ans = x+y;
    int x2 = x;
    int y2 = y;
    while(true) {
        bool flag = false;
        for(int i = 2; i <= min(x2,y2); i++) {
            if(x2%i==0 && y2%i==0) {
                x2/=i;
                y2/=i;
                flag = true;
                break;
            }
        }
        if(!flag) break;
    }
    ans -= x/x2 - 1;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3112
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <vector>
#include <stdio.h>
#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <cassert>

#define prev askdnsajd
#define rank asasdmdnasd
#define next lsjndajbs
#define hash asmdklansd
#define index asdklnas
#define right sld
#define left sldl
using namespace std;

typedef long long ll;
typedef long double dbl;

template<class T>
void print(vector<T> s){
    for (T x : s)
        cout << x << " ";
    cout << endl;
}

const int maxn = 10;

bool check[1000000];
int s[maxn][maxn];

int main(){
    srand(17);
    ios_base::sync_with_stdio(0);
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < 1000; i++)
    	check[i * i] = true;
    for (int i = 0; i < n; i++){
    	for (int j = 0; j < d; j++)
    		cin >> s[i][j];
    }
    int answer = 0;
    for (int i = 0; i < n; i++){
    	for (int j = i + 1; j < n; j++){
    		int t = 0;
    		for (int k = 0; k < d; k++)
    			t += (s[i][k] - s[j][k]) * (s[i][k] - s[j][k]);
    		if (check[t])
    			answer++;
    	}
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<iomanip>

#define INF 1<<29

using namespace std;

int main(void) {
	int n;
	cin >> n;
	vector<long long>dp(n + 2);
	for (int i = 0; i < n; i++) {
		dp[i] = 0;
	}
	dp[0] = 2;
	dp[1] = 1;
	if (n == 1) {
		cout << 1;
	}
	for (int i = 0; i < n; i++) {
		dp[i + 2] = dp[i + 1] + dp[i];
		if (i + 2 == n) {
			cout << dp[i + 2];
		}
	}
	return 0;
}

Measured memory_bytes: 256
a = [int(input()) for i in range(5)]
ans = 0
u = 0
o = 0
for i in range(5):
    ans += a[i]//10*10
    if a[i]%10 > 0:
        ans += 10
        if u==0:
            u=10
        u = min(u,a[i]%10)
        o = -10
print(ans+u+o)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define fo(i,a,b) for((i)=(a);i<=(b);i++)
#define rfo(i,a,b) for((i)=(a);i>=(b);i--)
#define inrange(x,y,z) (((x)>=(y))&&((x)<=(z)))
#define ALL(vec) (vec).begin(),(vec).end()
#define SOR(vec) sort(ALL(vec))
#define UNI(vec) (vec).erase(unique(ALL(vec)),(vec).end())
using namespace std;
int s;
long long res,MOD=1000000007;
long long inv[2020],fac[2020],ifac[2020];
void init_math(int N){
	inv[1]=1LL;
	for(int i=2;i<=N;i++)
		inv[i]=(MOD-((MOD/i)*inv[MOD%i])%MOD);
	fac[0]=1LL;
	ifac[0]=1LL;
	for(int i=1;i<=N;i++){
		fac[i]=(fac[i-1]*(long long)(i))%MOD;
		ifac[i]=(ifac[i-1]*inv[i])%MOD;
	}
}
long long C(int x,int y){
	return ((fac[x]*ifac[y])%MOD*ifac[x-y])%MOD;
}
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	init_math(s);
	for(int i=1;i<=s/3;i++){
		res+=C(s-i*2-1,i-1);
		if(res>MOD) res-=MOD;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3584
#include<stdio.h>

int main(void){
  long long i,j;
  int n,prime[50001];

  prime[0]=1;
  prime[1]=1;

  for(i=2;i<50001;i++)
    prime[i]=0;

  for(i=2;i<50001;i++){
    if(prime[i]==0){
      for(j=i*i;j<50001;j+=i)
	prime[j]=1;
    }
  }

  while(1){
    int count=0;
    scanf("%d",&n);
    if(n==0)break;    

    for(i=0;i<n/2+1;i++)
      if(prime[i]==0 && prime[n-i]==0)count++;
    
    printf("%d\n",count);
  }
  return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std ;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf pop_front()
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define rep(i,a,b) for(lli i=a;i<b;i++)
#define repe(i,a,b) for(lli i=a;i<=b;i++)
#define all(v) v.begin(), v.end()
#define mod 1000000009
#define inf 100000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<lli>
#define vii vector<int>
#define endl '\n'
#define pie  acosl(-1.0);
#define setp(k, x) fixed << setprecision(k) << (x)
#define deb(x) cerr << #x << ": " << x << " " << endl;
#define debug(x) cout << "m here-" <<#x<<" ..."<<"\n";
#define printa(a,n) for(lli i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
#define printv(a) for(lli i=0;i<a.size();i++) cout<<a[i]<<" "; cout<<"\n";
bool sortcol( const vector<lli>& v1, const vector<lli>& v2 ) //sort on basis of column //use- sort(vect.begin(), vect.end(),sortcol);
{ return v1[1] < v2[1]; }//[] o based indexing in column
bool sortpair(const pair<lli, lli> &a, const pair<lli, lli> &b)
{return a.second < b.second;}
struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

//////////////////////////////////////////////////////////////////////////////////////////////
void solve();

//////////////////////////////////////////////////////////////////////////////////////////////
//
// lli find_hash(string const& s){
// 	lli m = 10e8+7,p = 31,hash_value = 0,i,n,p_pow = 1;
//
// 	n = s.length();
//
// 	for(i = 0 ;i<n;i++){
// 		hash_value+= ((s[i]-'a'+1)*p_pow )%m;
// 		p_pow = p_pow *p;
// 	}
// 	return hash_value;
//
// }



int main ()
{
	// fastio
	lli  t;

	// cin>>t;
	// while(t--)
	{

		solve();

	}
}
///////////////////////////////////////////
void solve()
{
	long double n,i,d,a,b,c=0,j,k,x,y,check=0,m,len;
	cin>>n;
	a = ceil(n/1000);
	b = a*1000-n;
	cout<<b<<"\n";



}


Measured memory_bytes: 3792
#pragma GCC optimize ("O2")
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC diagnostic ignored "-Wunused-label"
#pragma GCC diagnostic ignored "-Wsign-compare"

#include <bits/stdc++.h>
using namespace std;

#define trav(a, A) for (auto & a : A)
#define f first
#define s second

typedef long long ll;

const ll MOD = 1e+9+7;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll MAXN = 1e+5+7;

void solve(){
    string s;
    cin >> s;
    cout << s;
    if (s.back() == 's') cout << "es\n";
    else cout << "s\n" ;
}

int main ()
{
	ios_base::sync_with_stdio (0);
	cin.tie (0);
	ll tc = 1; //cin >> tc;
	while (tc--)
	{
		solve();
	}

	return 0;
}




Measured memory_bytes: 3644
/**
  @file b.cpp
  @title
  @url https://atcoder.jp/contests/abc134/tasks/abc134_b
**/

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
#define ALL(obj) (obj).begin(), (obj).end()
#define REP(i, N) for (int i = 0; i < (N); ++i)

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

  cout << ceil((double)N / (double)(2 * D + 1)) << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define rep(i,a) for(int i = 0; i < a; i++)
using namespace std;

int main(){
	int n, a, b;
	int a_ans = 0, b_ans = 0;
	while(cin >> n, n){
		rep(i, n){
			cin >> a >> b;
			if(a > b){
				a_ans += (a + b);
			}else if(b > a){
				b_ans += (a + b);
			}else{
				a_ans += a;
				b_ans += b;
			}
		}
		cout << a_ans << " " << b_ans << endl;
		a_ans = 0; b_ans = 0;
	}
}

Measured memory_bytes: 1160
#include<stdio.h>
#include<stdlib.h>
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
  if(k < u->key) return treeSearch(u->left,k);
  else  return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y!=NIL && x==y->right){
    x = y;
    y = y->parent;
  }
    return y;
  
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  
  if(z->left == NIL || z->right == NIL) y=z;
  else y=treeSuccessor(z);
  if(y->left != NIL) x=y->right;
  else x=y->right;
  if(x != NIL) x->parent=y->parent;
  if(y->parent == NIL) root=x;
  else if(y == y->parent->left) y->parent->left=x;
  else y->parent->right=x;
  if(y != z) z->key=y->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x != NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }
    z->parent=y;
    if(y == NIL) root = z;
    else if(z->key < y->key) y->left=z;
    else y->right=z;
  
}

void inorder(Node u){
  if(u != NIL){
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
  }  
}
  
void preorder(Node u){
  if(u != NIL){
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  }
}
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  return 0;
}



Measured memory_bytes: 25148
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
int main(){
  set<int> p;
  p.insert(1);
  vector<int> a,b;
  long long int n,k,l,w=1,s;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    int j;
    cin>>j;
    a.push_back(j);
  }
  if(n<k){
  for(int i=1;i<k+1;i++){
    b.push_back(w);
    w=a.at(w-1);
    if(p.count(w)){
      l=i;
      break;
    }
    else{
      p.insert(w);
    }
  }
  for(int i=0;i<l;i++){
    if(b.at(i)==w){
      s=i;
      break;
    }
  }
  l=(k-s)%(l-s);
  cout<<b.at(s+l);}
  if(n>=k){
    for(int i=0;i<k;i++){

      w=a.at(w-1);
    }
    cout<<w;
  }
}

Measured memory_bytes: 12032
#include <bits/stdc++.h>
#define ll long long int 
using namespace std; 
ll dp[109][100009];
ll solve(ll wt[],ll val[],int w,int n)
{
    if(n<=0)
      return w==0 ? 0:INT_MAX;

    if(dp[n][w]!=-1)
    {
      return dp[n][w];
    }  
    ll ans=solve(wt,val,w,n-1);
    if(val[n-1]<=w)
      ans=min(wt[n-1]+solve(wt,val,w-val[n-1],n-1),ans);
   
    return dp[n][w]=ans;

}
int main() 
{ 
  ll n,w;
  cin>>n>>w;
  
  ll wt[n],val[n];
  ll maxv=0;
   memset(dp,-1,sizeof(dp));
  for(int i=0;i<n;i++)
  {
    cin>>wt[i]>>val[i];
    maxv+=val[i];
  }
  
  
  for(int i=maxv;i>=0;i--)
  {
    
    if(solve(wt,val,i,n)<=w)
    { 
     
      cout<<i;
      return 0;
     
    }
  }
  cout<<"0";

} 


Measured memory_bytes: 88764
#include <stdio.h>

int main(){
  int n,a[21],b,c[21],i,sum=0;
  
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
  for(i=1;i<=n;i++){
    scanf("%d",&b);
    sum += b;
  }
  for(i=1;i<n;i++)
    scanf("%d",&c[i]);
  
  for(i=1;i<n;i++)
    if(a[i]+1==a[i+1])
      sum += c[a[i]];
  
  printf("%d\n",sum);
  return 0;
}

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

using namespace std;

int dp[10][10];

int main() {
  for (;;) {
    int n, m = 0;
    cin >> n;
    if (!n) return 0;
    for (int i = 0; i < 10; i++)
      fill(dp[i], dp[i]+10, 1<<20);
    for (int i = 0; i < n; i++) {
      int a, b, c;
      cin >> a >> b >> c;
      m = max(m, max(a, b));
      dp[a][b] = c;
      dp[b][a] = c;
    }
    m++;
    for (int i = 0; i < m; i++)
      dp[i][i] = 0;
    for (int k = 0; k < m; k++)
      for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
    int rt = 0, rc = 1<<20;
    for (int i = 0; i < m; i++) {
      int c = 0;
      for (int j = 0; j < m; j++)
        c += dp[i][j];
      if (rc > c) {
        rt = i;
        rc = c;
      }
    }
    cout << rt << ' ' << rc << endl;
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
	int N, res = 0, max = 0;
  	cin >> N;
  	vector<int> H(N);
  	for(int i = 0; i < N; i++){
    	cin >> H[i];
    }
  
  	for(int i = 0; i < N; i++){
    	if(H[i] >= max){
          	max = H[i];
        	res++;
        }
    }
  	
  	cout << res << endl;
  	
	return 0;
}

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

long long nCr(int n, int r) {
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    int i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}

int main()
{
	int n,m;

	cin>>n>>m;

	int ans = 0;
	if(n>=2){
		ans += nCr(n,2);
	}

	if(m>=2){
		ans += nCr(m,2);
	}

	cout<<ans;

	

}

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

using namespace std;
typedef long long int lli;

const int MAXN = 200010;

int n, k, l;

int ind[MAXN];
int ans[MAXN];
int freq[MAXN];

bool marc[MAXN][2];

vector< int > component;

vector< int > adj[MAXN][2];

void DFS(int cur, int t, int root = 0)
{
	marc[cur][t] = true;
	
	if( t == 0 ) ind[ cur ] = root;
	else component.push_back( cur );

	for(int i = 0 ; i < adj[cur][t].size() ; i++)
	{
		int viz = adj[cur][t][i];

		if( !marc[viz][t] ) DFS( viz , t , root );
	}
}

int main()
{
	scanf("%d %d %d",&n,&k,&l);

	for(int i = 1 ; i <= k ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[ U ][0].push_back( V );
		adj[ V ][0].push_back( U );
	}

	for(int i = 1 ; i <= l ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[ U ][1].push_back( V );
		adj[ V ][1].push_back( U );
	}

	for(int i = 1 ; i <= n ; i++)
		if( !marc[i][0] ) DFS( i , 0 , i );

	for(int i = 1 ; i <= n ; i++)
	{
		if( marc[i][1] ) continue;

		DFS( i , 1 );

		for(int j = 0 ; j < component.size() ; j++)
		{
			int cur = component[j];
			freq[ ind[cur] ]++;
		}

		for(int j = 0 ; j < component.size() ; j++)
		{
			int cur = component[j];
			ans[cur] = freq[ ind[cur] ];
		}

		for(int j = 0 ; j < component.size() ; j++)
		{
			int cur = component[j];
			freq[ ind[cur] ]--;
		}

		component.clear();
	}

	for(int i = 1 ; i <= n ; i++)
		printf("%d ",ans[i]);
}

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

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

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

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int left = a + b;
  int right = c + d;
  if (left > right) {
    cout << "Left" << endl;
  } else if (left == right) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
def main():
    x,y = map(int,input().split())
    ans = 0
    if x==0 :
        ans = abs(x-y)
        if y < 0:
            ans +=1
        print(ans)
        return
    elif y == 0:
        ans = abs(x-y)
        if x> 0:
            ans += 1
        print(ans)
    elif (x>=0 and y >= x) or (y<=0 and x<=y):
        print(abs(y-x))
        return
    elif (y>=0 and x >= y) or (x<=0 and y<=x):
        print(abs(y-x) + 2)
        return
    elif (x>0 and y<0)or(x<0 and y>0):
        print(abs(abs(y)-abs(x))+1)
    # print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
button = [
    ["", "", ""],
    [".", ",", "!", "?", " "],
    ["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"],
]

N = int(input())
for _ in range(N):
    S = ""
    count = 0
    l = list(input())
    for i in range(0, len(l)):
        if l[i] == "0":
            S += button[int(l[i - 1])][count-1]
            count = 0
        else:
            # print(l[i])
            count = (count + 1) % len(button[int(l[i])])
    print(S)



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

typedef long long int ll;
typedef unsigned long long int ull;

int main() {
  int x;

  for (int i = 0; i < 5; i++) {
    cin >> x;
    if (x == 0) {
      cout << i + 1 << endl;
      break;
    }
  }
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long a,b,c,d;
  cin>>a>>b>>c>>d;
  vector<long long>v;
  v.push_back(a*c);
  v.push_back(a*d);
  v.push_back(b*c);
  v.push_back(b*d);
  sort(v.begin(),v.end(),greater<long long>());
  cout<<v[0];
  
}


Measured memory_bytes: 3620
def f(l):
 return map(lambda x: (x[0] + x[1]) % 10, zip(l[:len(l)-1], l[1:]))

while True:
 try:
  l = map(int, raw_input().strip());
  for i in range(9):
   l = f(l)
  print l[0]
 except:
  break;

Measured memory_bytes: 4204
//  Created by conan1024hao in 2020.
//  Copyright © 2020 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e17
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
bool color[1001][1001];ll m[30];
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;string s;cin>>n>>s;
    ll ans=1;
    
    for(int i=0;i<n;i++){
        m[s[i]-'a']++;
    }
    for(int i=0;i<26;i++)
    {
        ans*=m[i]+1;
        ans%=MOD;
    }
    cout<<ans-1<<Endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------








Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define _GLIBCXX_DEBUG
using namespace std;

int main() {
    string so,to;
    cin >> so >> to;
    int ss = so.size();
    int tt = to.size();
    char s[ss],t[tt];
    rep(i,ss) s[i] = so[ss-1-i];
    rep(i,tt) t[i] = to[tt-1-i];
    auto pos = [](char s,char t) {
        if(s == '?') return true;
        else {
            if(s == t) return true;
            else return false;
        }
    };
    bool flag = false;
    rep(i,ss-tt+1) {
        bool flag2 = true;
        rep2(j,i,i+tt) {
            if(!pos(s[j],t[j-i])) flag2 = false;
        }
        if(flag2) {
            flag = true;
            rep(k,tt) s[i+k] = t[k];
            break;
        }
    }
    if(flag) {
        for(int i = ss-1; i >= 0; i--) {
            if(s[i] == '?') cout << 'a';
            else cout << s[i];
        }
    } else {
        cout << "UNRESTORABLE";
    }
}

Measured memory_bytes: 384
n = int(input())

dp = [[0]*16 for i in range(n)]
for j in range(16):
  dp[1][j] = 1

for i in range(2,n):
  for j in range(16):
    k = j//4
    dp[i][j] = dp[i-1][k]+dp[i-1][k+4]+dp[i-1][k+8]+dp[i-1][k+12]
    if j == 1:
      dp[i][j] -= dp[i-1][8]
    elif j == 6:
      dp[i][j] -= dp[i-1][1]
    elif j == 9:
      dp[i][j] -= dp[i-1][2]+dp[i-2][2]+dp[i-2][3]
    elif j == 13:
      dp[i][j] -= dp[i-2][2]
    else:
      continue

count = 0
for j in range(16):
  count += dp[n-1][j]

print(count%1000000007)

Measured memory_bytes: 39664
def abc153_e():
    H, N = map(int, input().split())
    M = [tuple(map(int, input().split())) for _ in range(N)]

    inf = 10**18
    cost = [inf] * (H+1)
    cost[0] = 0
    for a, b in M:
        for i in range(1, H+1):
            tmp = cost[i-a] + b if i-a > 0 else b
            cost[i] = min(cost[i], tmp)
    print(cost[H])

abc153_e()

Measured memory_bytes: 41072
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static int[][] cells;
	private static final int S = 1;
	private static final int M = 2;
	private static final int L = 3;

	/*** ????????? */
	static {
		cells = new int[14][14];
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	/**
	 * ?????????????????????
	 *
	 * @param args
	 *            ??????????????°
	 */
	public static void main(String[] args) throws IOException {
		String line;
		int x, y, size, blindNum = 0, max = 0;

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			StringTokenizer st = new StringTokenizer(line, ",");
			x = Integer.parseInt(st.nextToken()) + 2;
			y = Integer.parseInt(st.nextToken()) + 2;
			size = Integer.parseInt(st.nextToken());
			set(x, y, size);
		}
		for (x = 2; x < 12; x++) {
			for (y = 2; y < 12; y++) {
				int cell = cells[x][y];
				if (cell == 0) {
					blindNum++;
				}
				if (max < cell) {
					max = cell;
				}
			}
		}
		System.out.println(blindNum + "\n" + max);
	}

	/**
	 * ??\????????????????????????????????´????¨??????????<br>
	 *
	 * @param x
	 *            ???
	 * @param y
	 *            ???
	 * @param size
	 *            ??´?????§??????
	 *
	 */
	private static void set(int x, int y, int size) {
		cells[x][y]++;
		if (size >= S) {
			cells[x - 1][y]++;
			cells[x + 1][y]++;
			cells[x][y - 1]++;
			cells[x][y + 1]++;
		}
		if (size >= M) {
			cells[x - 1][y - 1]++;
			cells[x - 1][y + 1]++;
			cells[x + 1][y - 1]++;
			cells[x + 1][y + 1]++;
		}
		if (size >= L) {
			cells[x - 2][y]++;
			cells[x + 2][y]++;
			cells[x][y - 2]++;
			cells[x][y + 2]++;
		}
	}
}

Measured memory_bytes: 15028
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e6+5;
vector<long long> v1[MAXN];
vector<long long> v2[MAXN];
priority_queue<pair<long long,long long>> pq;
bool visited[MAXN];
long long k[MAXN];
long long l[MAXN];
long long r[MAXN];

int main() {
    long long t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        for(long long i=1;i<=n;i++){
            v1[i].clear();
            v2[i].clear();
        }
        for(long long i=1;i<=n;i++){
            cin>>k[i]>>l[i]>>r[i];
            visited[i] = false;
            v1[k[i]].push_back(i);
            v2[k[i]+1].push_back(i);
        }
         while(pq.size()){
            pq.pop();
        }
        for(long long i=n;i>=1;i--){
            for(long long x:v1[i]){
                pq.push(make_pair(l[x]-r[x],x));
                
            }
            if(pq.size()){
                    auto hold = pq.top();
                    pq.pop();
                    if(hold.first>0){
                        
                        visited[hold.second] = true;
                    }
                }
        }
        while(pq.size()){
            pq.pop();
        }
        for(long long i=1;i<=n;i++){
            for(long long x:v2[i]){
                pq.push(make_pair(r[x]-l[x],x));
                //cout<<i<<" "<<r[i]-l[i]<<endl;
            }
            if(pq.size()){
                    auto hold = pq.top();
                    pq.pop();
                    
                    if(hold.first>0){
                        
                        visited[hold.second] = true;
                    }
                    
                }
        }
        long long ans = 0;
        for(long long i=1;i<=n;i++){
            if(visited[i]){
                ans+=max(l[i],r[i]);
            }else{
                ans+=min(l[i],r[i]);
            }
        }
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 64408
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = 0;
		String s = sc.next();
		char[] a = s.toCharArray();
		int max = 0;
		
		if(a.length==1) {
			if(a[0] == 'A' || a[0] == 'C' || a[0] == 'G' || a[0] == 'T') {
				System.out.println(1);
				System.exit(0);
			}
			else {
				System.out.println(0);
				System.exit(0);
			}
			
		}
		

		for (int i = 0; i < a.length - 1; i++) {
			count = 0;
			if (a[i] == 'A' || a[i] == 'C' || a[i] == 'G' || a[i] == 'T') {
				count++;
			}
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] == 'A' || a[j] == 'C' || a[j] == 'G' || a[j] == 'T') {
					count++;
				} else {
					j = a.length;
				}
			}
			max = Math.max(max, count);
		}
		System.out.println(max);

		sc.close();
	}
}


Measured memory_bytes: 21460
int main()
{
  int n;
  scanf("%d", &n);
  int a[n];
  int dansa = 0, kakaku = 200;
  long sum = 1000, buy = 0;
  int i;
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);
  i = 1;
  while (i < n)
  {
    if (a[i - 1] >= a[i])
      i++;
    else
    {
      buy = sum / a[i - 1];
      sum += (a[i] - a[i - 1]) * buy;
      i++;
    }
  }
  /*
  for (i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
    if (a[i] < kakaku)
      kakaku = a[i];
    if (i >= 1 && a[i] != a[i - 1])
      dansa = a[i - 1];
    if (i >= 1 && a[i] > dansa) 
    {
      buy = sum / kakaku;
      sum += (a[i] - kakaku) * buy;
      kakaku = 200;
    }
  }
  */
  printf("%ld", sum);
}

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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rep1r(i, n) for (int i = ((int)(n)); i > 0; --i)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

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

    int n;
    cin >> n;
    vi s(n);
    rep(i, n) { cin >> s[i]; }

    int q;
    cin >> q;
    int cnt = 0;
    while (q--) {
        int t;
        cin >> t;
        auto result = find(all(s), t);
        if (result != s.end()) {
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}



Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,an=0;
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		{
			int p=0;
			for (int j=1;j<=i;j++)
				if (i%j==0) p++;
			if (p==8 && i%2==1) an++;
		}
	cout<<an;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

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

  int h, w; cin >> h >> w;
  rep(i, h) {
    string s; cin >> s;
    cout << s << endl;
    cout << s << endl;
  }
}

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

int main()
{
    int x,a,b,c,ans=0;cin>>a>>b>>c;
    for (int i=1;i<=a;++i) {
        cin>>x;
        if (x<b||x>=c) ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl "\n"
#define pii tuple<ll,ll,ll>
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
const ll N=1005;
const ll INF=LLONG_MAX;
void amfetamin()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
}
int main()
{
amfetamin();
char c;
cin>>c;
if ('A'<=c && c<='Z')
    cout<<'A';
else
    cout<<'a';

}


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

using namespace std;

int main()
{
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;
	if (a == 0) cout << 1;
	if (b == 0) cout << 2;
	if (c == 0) cout << 3;
	if (d == 0) cout << 4;
	if (e == 0) cout << 5;
	return 0;
}

Measured memory_bytes: 3560
#include <stdio.h>
 
int main(){
    int a,b,c;
    int i,j=0;
    scanf("%d %d %d",&a,&b,&c);
    for(i=0; i<b-a+1; i++){
        if(c%(a+i) == 0){
            j++;
        }
    }
    printf("%d\n",j);
    return 0;
}

Measured memory_bytes: 596
N,K=map(int,input().split())
if K>(N-1)*(N-2)//2:
    print(-1)
else:
    ans=(N-1)*(N-2)//2-K
    print(ans+N-1)
    node=[]
    for i in range(2,N+1):
        node.append((1,i))
    count=0
    for i in range(2,N):
        for j in range(i+1,N+1):
            if count<=ans:
                node.append((i,j))
                count+=1
            else:
                break
    for i in range(ans+N-1):
        print(*node[i])

Measured memory_bytes: 3992
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int32_t main(){

    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

    int a;
    string s;
    cin>>a>>s;
    if(a>=3200) cout<<s<<endl;
    else cout<<"red"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m)
    os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL N;
  cin>>N;
  cout<<N*(N-1)/2<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    int n;
    cin >> n;
    string s[n];
    rep(i, n) { cin >> s[i]; }
    set<string> hina;

    rep(i, n) { hina.insert(s[i]); }

    if (hina.size() == 3) {
        cout << "Three" << endl;
    } else {
        cout << "Four" << endl;
    }
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define lop(i,a,b) for(ll i=a;i<b;i++)
using namespace std;

void func(){
    ll n;
    cin>>n;
    vector<char> a;
    while(n>0){
        n--;
        a.push_back((char)(97+(n%26)));
        n/=26;
    }
    for(int i=a.size()-1;i>=0;i--)cout<<a[i];
    cout<<endl;
}

int main(){
    fastio;
    int t=1;
    //cin>>t;
    while(t--){
        func();
    }
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

#define ll (long long)
#define REP(i,n) for(int i = 0;i<(int)n;i++)
#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (a);i>(b);i--)

using namespace std;

/*thief??????*/

int main(void){
    
    char str[210] = {};
    char copy[210] = {};
    int i = 0;
    gets(str);
    while(*(str+i))
    {
        *(copy+i) = toupper(*(str+i));
        i++;
    }
    printf("%s\n",copy);
    return 0;
    
}

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

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);

const int N = 1005;

int main() {

	FAST;

	int a, b;
	cin >> a >> b;
	for (int i = 1; i <= 1250; i ++) {
		if (int(double(i * 0.08)) == a && int(double(i * 0.1)) == b) {
			cout << i << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
	return 0;
}


Measured memory_bytes: 256
from math import gcd
from functools import reduce
from collections import Counter
from itertools import chain


# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            while n % i == 0:
                n //= i
            yield i
    if n > 1:
        yield n


def solve(A):
    d = reduce(gcd, A)
    if d != 1:
        return 'not coprime'

    A.sort()

    s = set()
    for a in A:
        for p in prime_factors(a):
            if p in s:
                return 'setwise coprime'
            else:
                s.add(p)

    return 'pairwise coprime'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int,input().split()))

    print(solve(A))


Measured memory_bytes: 183704
n = int(input())

g = [[] for _ in range(n)]

for i in range(n):
    m = int(input())
    for _ in range(m):
        x, y = map(int, input().split())
        g[i].append((x-1, y))

ans = 0

for i in range(1, 2 ** n):
    ok = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for x, y in g[j]:
            if (i >> x)& 1 != y:
                ok = False
                break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int ff;
int n,m,col[500100],blo,tot,le,ri,ans[500100],cnt[500100];
pair<pair<int,int>,int> que[500100];
bool pp(pair<pair<int,int>,int> x,pair<pair<int,int>,int> y){
	return x.first.second<y.first.second;
}
inline void inser(int val){cnt[val]++;if(cnt[val]==1) ff++;}
inline void eras(int val){cnt[val]--;if(cnt[val]==0) ff--;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&col[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&que[i].first.first,&que[i].first.second);
		que[i].second=i;
	}
	sort(que+1,que+m+1);
	blo=max(1,(int)(sqrt(m)));
	tot=(m+blo-1)/blo;
	for(int i=1;i<=tot;i++){
		le=blo*(i-1)+1;
		ri=min(blo*i,m);
		sort(que+le,que+ri+1,pp); 
		for(int j=1;j<=n;j++) cnt[j]=0;
		ff=0;
		for(int j=que[le].first.first;j<=que[le].first.second;j++)
			inser(col[j]);
		ans[que[le].second]=ff;
		for(int j=le+1;j<=ri;j++){
			for(int kk=que[j-1].first.first;kk<que[j].first.first;kk++)
				eras(col[kk]);
			for(int kk=que[j].first.first;kk<que[j-1].first.first;kk++)
				inser(col[kk]);
			for(int kk=que[j-1].first.second+1;kk<=que[j].first.second;kk++)
				inser(col[kk]);
			ans[que[j].second]=ff;
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}


Measured memory_bytes: 15444
import heapq

def dijkstra(s):
	hq = [(0, s)]
	heapq.heapify(hq) # リストを優先度付きキューに変換
	cost = [float('inf')] * n # 行ったことのないところはinf
	cost[s] = 0 # 開始地点は0
	while hq:
		c, v = heapq.heappop(hq)
		if c > cost[v]: # コストが現在のコストよりも高ければスルー
			continue
		for d, u in e[v]:
			tmp = d + cost[v]
			if tmp < cost[u]:
				cost[u] = tmp
				heapq.heappush(hq, (tmp, u))
	return cost

n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
	a,b,c = map(int,input().split())
	a,b = a-1, b-1
	e[a].append((c, b))
	e[b].append((c, a))
q,k = map(int,input().split())
l = dijkstra(k-1)
for _ in range(q):
	x,y = map(int,input().split())
	print(l[x-1] + l[y-1])

Measured memory_bytes: 102860
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <algorithm>

typedef long long ll;
const ll MOD = 1e9 + 7;
const long long INF = 1LL<<60;
const double PI=3.14159265358979323846;
const int NMAX=100005;
using namespace std;

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

    sort(a.begin(),a.end());
    sort(b.begin(),b.end());

    ll ans = 0;
    if(n%2 == 1){
        ans = b[(n+1)/2-1]-a[(n+1)/2-1]+1;
    } else {
        double aa = (a[(n/2)-1]+a[(n/2)])/2.0;
        double bb = (b[(n/2)-1]+b[(n/2)])/2.0;
        ans = ll((bb-aa)*2.0) + 1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 6420
#include<iostream>

using namespace std;
int main(){

//for(int i=0; i<3; i++){
int h, m, s, H, M, S, T;
	for(int i=0; i<3; i++){
		cin >> h >> m >> s >> H >> M >> S;
		T = (3600*H + 60*M + S)-(3600*h + 60*m + s);
			cout << T/3600 << " ";
			cout << T%3600/60 << " ";
			cout << T%60 << endl;
	}
	
//	for(int i=0; i<3; i++){
		
	


	return 0;



}


Measured memory_bytes: 3096