akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define m 1000000007
using namespace std;
int main()
{
    int n;
    cin>>n;
    int dp[n+1];
    if(n<=2)
    {
        cout<<0;
        return 0;
    }
    dp[0]=0,dp[1]=0,dp[2]=0;
    for(int i=3;i<=n;i++)
    {
        dp[i]=1;
        for(int j=3;j<=i;j++)
        {
            dp[i]=(dp[i]%m+dp[i-j]%m)%m;
        }
    }
    cout<<dp[n]%m;
    return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<ctype.h>
#include<math.h>
#define PI 3.14159265359
#define N_MAX 1000
#define NUM 1000
#define min(x,y) x < y ? x : y
#define max(x,y) x > y ? x : y

void trace(int A[], int n)
{
  int i;
  for(i = 1; i <= n; i++)
    {
      if(i > 1) printf(" ");
      printf("%d",A[i]);
    }
  printf("\n");
}

int main()
{
  int n, i, j, tmp;
  int A[N_MAX+1];
  scanf("%d",&n);
  for(i = 1; i <= n; i++) scanf("%d",&A[i]);
  trace(A,n);
  for(j = 2; j <= n; j++)
    {
      tmp = A[j];
      i = j - 1;
      while(i > 0 && A[i] > tmp)
	{
	  A[i+1] = A[i];
	  i--;
	}
      A[i+1] = tmp;
      trace(A,n);
    }
  return 0;
}

Measured memory_bytes: 608
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <functional>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define MOD (long long int)(1e9+7)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  if(n <= 1e7){
    ret *= kaijo(n); ret %= MOD;
    ret *= gyaku_kaijo(r); ret %= MOD;
    ret *= gyaku_kaijo(n-r); ret %= MOD;
  }else{
    rep(i,r){
      ret *= n-i; ret %= MOD;
      ret *= mpow(r-i, MOD-2); ret %= MOD;
    }
  }
  return ret;
}

int main(void){
  fast_io
  cout<<fixed<<setprecision(15);
  vector<string> S;
  int h,w;cin>>h>>w;
  rep(i,h){
    string s;cin>>s;
    S.push_back(s);
  }
  int dp[102][102] = {};
  rep(i,102){
    rep(j,102){
      dp[i][j] = INF;
    }
  }
  if(S[0][0] == '#'){
    dp[1][1] = 1;
  }else{
    dp[1][1] = 0;
  }
  reps(i,h){
    reps(j,w){
      dp[i][j] = min({dp[i][j], dp[i-1][j] + (i >= 2 && S[i-1-1][j-1] == S[i-1][j-1] ? 0 : 1),
                                dp[i][j-1] + (j >= 2 && S[i-1][j-1-1] == S[i-1][j-1] ? 0 : 1)});
    }
  }

  cout<<(dp[h][w]+1)/2<<endl;
}

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

typedef long long ll;
const ll mod=1e9+7;
const ll N=20003;
const ll INF=1e10;

vector<vector<ll>> pt(20005,vector<ll> (2005));
ll s,k;

void f(){
	pt[0][0]=1;
	for(int i=1;i<=s-3;i++){
		pt[i][0]=1;
		for(int j=1;j<=i;j++) pt[i][j]=(pt[i-1][j]+pt[i-1][j-1])%mod;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cin>>s;
	k=s/3;
	f();
	ll ans=0;
	for(int i=1;i<=k;i++) ans=(ans+pt[s-2*i-1][i-1])%mod;
	cout<<ans;
}	  


Measured memory_bytes: 317312
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
#include<functional>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define erep(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

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


Measured memory_bytes: 256
#pragma region template 2.4
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using pq_asc = priority_queue<T, vector<T>, greater<T>>;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP1(i, n) for (ll i = 1; i <= (n); ++i)
#define FOR(i, a) for (auto &i : a)
#define CH(f, x, y) x = f(x, y)
#define IN(T, x) \
    T x;         \
    cin >> x;
#define AIN(T, a, n) \
    vector<T> a(n);  \
    FOR(i, a)        \
    cin >> i;
#define A2IN(T1, a, T2, b, n) \
    vector<T1> a(n);          \
    vector<T2> b(n);          \
    REP(i, n)                 \
    cin >> a[i] >> b[i];
#define OUT(x) cout << (x) << endl;
#define FOUT(x) cout << fixed << setprecision(15) << (x) << endl;
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define DUMPA(a)          \
    cout << #a << " = {"; \
    JOUT(ALL(a), ", ", cout) << "}" << endl;

template <typename T>
ostream &JOUT(T s, T e, string sep = " ", ostream &os = cout)
{
    if (s != e)
    {
        os << *s;
        ++s;
    }
    while (s != e)
    {
        os << sep << *s;
        ++s;
    }
    return os;
}

ostream &YES(bool cond, string yes = "Yes", string no = "No", ostream &os = cout)
{
    if (cond)
    {
        os << yes << endl;
    }
    else
    {
        os << no << endl;
    }
    return os;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << '(' << p.first << ", " << p.second << ')';
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << '[';
    JOUT(ALL(v), ", ", os) << ']';
    return os;
}

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#pragma endregion template

int main()
{
    IN(ll, n);
    AIN(string, S, n);
    vi C(26, INF);
    FOR(s, S)
    {
        vi c(26);
        FOR(x, s)
        {
            ++c[x - 'a'];
        }
        REP(i, 26)
        {
            CH(min, C[i], c[i]);
        }
    }
    string ans;
    REP(i, 26)
    {
        if (C[i] == INF)
        {
            C[i] = 0;
        }
        REP(j, C[i])
        {
            ans.push_back('a' + i);
        }
    }
    OUT(ans);
}

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

#define FORi(i, a, b) for(int i = a; i < b; ++i)
#define FORd(i, a, b) for(int i = a; i > b; --i)
 
   
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    
    if(a <= b) {
        if(c <= b) {
            cout << (a + c) << endl;
        }
        else {
            cout << (a + b) << endl;
        }
    }
    else {
        if(c <= a) {
            cout << (b + c) << endl;
        }
        else {
            cout << (b + a) << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
from heapq import *


def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D[-1] if D[-1]!=INF else -1


N, M, *L = map(int, open(0).read().split())
G = [[(i - 1, 0)] for i in range(N)]
G[0] = []
for l, r, c in zip(*[iter(L)] * 3):
	G[l - 1].append((r - 1, c))
print(Dijkstra(G))


Measured memory_bytes: 52428
#include"bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int, int> P;
int a[300005];
int s1[300005], s2[300005];
signed main() {
	int n; cin >> n;
	rep(i, n + n + n)cin >> a[i];
	priority_queue<int, vector<int>, greater<int>>Q1;
	rep(i, n) {
		s1[n - 1] += a[i]; Q1.push(a[i]);
	}
	for (int i = n; i < n + n; i++) {
		Q1.push(a[i]);
		s1[i] = s1[i - 1] + a[i];
		s1[i] -= Q1.top(); Q1.pop();
	}
	
	priority_queue<int>Q2;
	rep(i, n) {
		s2[n + n] += a[n + n + n - 1 - i];
		Q2.push(a[3 * n - 1 - i]);
	}
	for (int i = n + n - 1; i >= n; i--) {
		s2[i] = s2[i + 1] + a[i];
		Q2.push(a[i]);
		s2[i] -= Q2.top(); Q2.pop();
	}
	int ans = -1e18;
	for (int i = n - 1; i < n + n; i++)ans = max(ans, s1[i] - s2[i + 1]);
	cout << ans << endl;
}

Measured memory_bytes: 7796
import copy

k = int(input())

lun = [1,2,3,4,5,6,7,8,9]
tlun = []
tlun = copy.deepcopy(lun)
length = 2
while len(lun) < k:
    tmp = []
    for x in tlun:
        y = str(x)
        xt = int( y[-1] )
        a = xt + 1
        b = xt - 1
        if b != -1:
            lun.append(int(y+str(b)))
            tmp.append(int(y+str(b)))
        
        lun.append(int(y+str(xt)))
        tmp.append(int(y+str(xt)))

        if a != 10:
            lun.append(int(y+str(a)))
            tmp.append(int(y+str(a)))
        

    tlun = copy.deepcopy(tmp)

# lun.sort()
print(lun[k-1])

        

    






Measured memory_bytes: 21656
#include <stdio.h>
#include <iostream>
#include <string>
#define NUM 10000000
#define NIL -1
#define ll long long

using namespace std;

ll heap[NUM];
int H;

void increaseKey(int index){
    if(index == 1)
        return;
    
    if(heap[index / 2] < heap[index]){
        swap(heap[index / 2], heap[index]);
        increaseKey(index / 2);
    }

    return;
}

void maxHeapify(int index){
    int max_index;
    if(heap[index * 2] < heap[index * 2 + 1]){
        max_index = index * 2 + 1;
    }else{
        max_index = index * 2;
    }

    if(heap[max_index] > heap[index]){
        swap(heap[index], heap[max_index]);
        maxHeapify(max_index);
    }

    return;
}

void insert(ll num){
    H++;
    heap[H] = num;
    increaseKey(H);
}

void extract(){
    printf("%lld\n", heap[1]);
    swap(heap[1], heap[H]);
    heap[H] = NIL;
    H--;

    maxHeapify(1);
}

void init(){
    H = 0;
    for(int i = 0; i < NUM; i++){
        heap[i] = NIL;
    }
}

int main(void){
    init();

    string s;
    cin >> s;

    while(s != "end"){
        if(s == "insert"){
            ll num;
            scanf("%lld", &num);
            insert(num);
        }else if(s == "extract"){
            extract();
        }else{
            printf("unknow command\n");
        }

        cin >> s;
    }

    return 0;
}



Measured memory_bytes: 81440
a,b,c,d = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

while True:
	
	c -= b
	if c<=0:
		ans="Yes"
		break
	
	a -= d
	if a<=0:
		ans="No"
		break

print(ans)



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

int main(){
  int N,A,B,count=0;
  cin >> N >>A >>B;
  for(int i=0;i<N;i++){
    int C=i+1,sum=0;
    for(int j=0;j<6;j++){
      sum+=C%10;
      C/=10;
    }
    if(A<=sum && sum<=B){
      count+=i+1;
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=505;
int n,a[N],ans[N*N];
PI b[N];
int main(){
	n=read();
	for(int i=1;i<=n;i++){ans[a[i]=read()]=i; b[i]=mp(a[i],i);}
	sort(&b[1],&b[n+1]);
	int dq=1;
	for(int i=1;i<=n;i++){
		int t=b[i].second;
		for(int j=1;j<t;j++){
			while(ans[dq])if(ans[dq++]==t){puts("No"); return 0;}
			ans[dq++]=t;
		}
	}
	dq=n*n;
	for(int i=n;i;i--){
		int t=b[i].second;
		for(int j=t+1;j<=n;j++){
			while(ans[dq])if(ans[dq--]==t){puts("No"); return 0;}
			ans[dq--]=t;
		}
	}
	puts("Yes");
	for(int i=1;i<=n*n;i++){
		write(ans[i]); putchar(' ');
	}
}

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

n, m, *x = map(int, read().split())

if n >= m:
    print('0')
    exit()

x = sorted(x)
l = sorted([x[i + 1] - x[i] for i in range(m-1)])

print(sum(l[:m-n:]))


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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<8;i++){
        int t;
        if(a>b){
           t=a;
           a=b;
           b=t;
        }
        if(b>c){
            t=b;
            b=c;
            c=t;
        }
    }
    cout<<a<<" "<<b<<" "<<c<<endl;
}






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

def main():
    na = list(map(int, input().split()))
    N, C = na[0], na[1]

    D = []
    for i in range(C):
        D.append(list(map(int, input().split())))
    c = []
    for i in range(N):
        c.append(list(map(int, input().split())))

    s = []
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))

    for i in range(N):
        for j in range(N):
            m = (i + j) % 3
            for k in range(1, C + 1):
                s[m][k] += D[c[i][j] -1][k - 1]

    s_min = 500 * 500 * 1000
    for i in range(1, C + 1):
        for j in range(1, C + 1):
            if i == j:
               continue 
            for k in range(1, C + 1):
                if i == k or j == k:
                    continue
                s_min = min(s_min, s[0][i] + s[1][j] + s[2][k])


    print(s_min)


if __name__ == '__main__':
    main()



Measured memory_bytes: 7540
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++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(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    string s;
    cin >> s;
    string sa=s.substr(0,s.length()/2);
    string sb=s.substr(s.length()/2+1,s.length()/2);
    REP(i,s.length()/2){
        if(s[i]!=s[s.length()-i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    REP(i,sa.length()/2){
        if(sa[i]!=sa[sa.length()-i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    REP(i,sb.length()/2){
        if(sb[i]!=sb[sb.length()-i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<complex>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
	int n;
	cin>>n;
	int k=0,r=n;
	while(r){
		k+=r%10;
		r/=10;
	}
	cout<<(n%k==0?"Yes":"No")<<endl;
	return 0;
}


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

int main(){
	int n,l;
	queue<int> que; 
	int a[100000];
	int time[100000] = {};
	cin >> n >> l;
	for(int i = 0;i < n;i++) cin >> a[i];
	for(int i = 0;i < n;i++){
		if((i == 0 && a[i] > a[i + 1]) || (i == n - 1 && a[i] > a[i - 1]) || (a[i] > a[i - 1] && a[i] > a[i + 1])) que.push(i);
	}
	while(!que.empty()){
		int num = que.front();que.pop();
		if(time[num] != 0) continue;
		if(!((num == 0 && a[num] > a[num + 1]) || (num == n - 1 && a[num] > a[num - 1]) || (a[num] > a[num - 1] && a[num] > a[num + 1]))) continue;
		if(num == 0) {
			time[num] = time[num + 1] + l - a[num];
			que.push(num + 1);
		}
		else if(num == n - 1) {
			time[num] = time[num - 1] + l - a[num];
			que.push(num - 1);
		}
		else {
			time[num] = max(time[num - 1],time[num + 1]) + l - a[num];
			que.push(num - 1);
			que.push(num + 1);
		}
		a[num] = 0;
		//cout << num << " " << time[num] << endl;
	}
	int ma = 0;
	for(int i = 0;i < n;i++) ma = max(ma,time[i]);
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 4036
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
  double xa,ya,xb,yb,xc,yc,xd,yd,lx1,lx2,ly1,ly2,a1,a2;
  while(cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd){
    if((yb-ya)*(yd-yc)==-1*(xb-xa)*(xd-xc)) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
}


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

using namespace std;

struct basedEXORSET {
    unsigned long long base[64];
    basedEXORSET(){
        memset(base,0,sizeof(base));
    }
    unsigned long long cul(unsigned long long x){
        unsigned long long one = 1;
        for(int i = 0;i < 64;i++){
            if(x & (one << i)){
                x ^= base[i];
            }
        }
        return x;
    }
    void add(unsigned long long x){
        x = cul(x);
        if(x){
            base[__builtin_ctzll(x)] = x;
        }
    }
    bool has(unsigned long long x){
        return cul(x) == 0;
    }
};

int n;

void solve(){
    int i,j;
    string str;
    cin >> n;
    vector<unsigned long long> a(n);
    for(i = 0;i < n;i++) cin >> a[i];
    cin >> str;
    basedEXORSET bes;
    for(i = n-1;i >= 0;i--){
        if(str[i] == '0'){
            bes.add(a[i]);
        }
        else{
            if(bes.cul(a[i])){
                cout << 1 << endl;
                return;
            }
        }
    }
    cout << 0 << endl;
}

int main(){
    int t;
    cin >> t;
    for(int i = 0;i < t;i++){
        solve();
    }
}


Measured memory_bytes: 3572
import java.io.{BufferedReader, InputStream, InputStreamReader}
import java.util.{Comparator, StringTokenizer}

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}
import scala.collection.mutable.{ArrayBuffer, ListBuffer}

object Main {
  val MOD = 1000000007
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val N, C = sc.nextInt()
    type Schedule = (Int, Int)
    val schedules = Array.fill[ArrayBuffer[Schedule]](C)(ArrayBuffer())
    (0 until N) foreach { _ =>
      val s, t = sc.nextInt()
      val c = sc.nextInt() - 1
      schedules(c) += ((s, t))
    }

    val d = Array.ofDim[Int](200002)
    (0 until C) foreach { c =>
      iterateMergedSchedule(c) { case (s, t) =>
        d(s * 2 - 1) += 1
        d(t * 2) -= 1
      }
    }

    def iterateMergedSchedule(c: Int)(f: Schedule => Unit): Unit = {
      val sorted = schedules(c).sortBy(_._1)
      val n = sorted.length
      def step(i: Int, prev: Schedule): Unit = {
        if (i == n) f(prev)
        else {
          val cur = sorted(i)
          if (prev._2 == cur._1) step(i + 1, (prev._1, cur._2)) // merge
          else {
            f(prev)
            step(i + 1, cur)
          }
        }
      }

      if (sorted.nonEmpty) step(1, sorted.head)
    }

    (0 until d.length - 1) foreach { i =>
      d(i + 1) += d(i)
    }

    val ans = d.max
    println(ans)
  }


  def main(args: Array[String]): Unit = {
    solve()
  }


  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
    def nextLong(): Long = next.toLong
    def nextChar(): Char = next.charAt(0)
  }

}


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

using namespace std;

int n;
int a[123];

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int ans = 0;
  int i = 0;
  while (i < n) {
    int j = i;
    while (j + 1 < n && a[i] == a[j + 1]) {
      j++;
    }
    ans += (j - i + 1) / 2;
    i = j + 1;
  }
  printf("%d\n", ans);
  return 0;
}

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

int main(){
    string s;
    vector<string> v;
    while(cin>>s){
        v.push_back(s);
    }
    sort(v.begin(),v.end());
    int l=0;
    for(int i=0;i<(int)v.size();i++){
        if(v[i].size() > v[l].size())l=i;
    }
    int f=0,fmax=0;
    for(int i=0;i<(int)v.size();i++){
        int j=i;
        while(j<(int)v.size() && v[i]==v[j])j++;
        if(j-i > fmax){
            fmax = j;
            f = i;
        }
        i=j;
    }
    cout << v[f] << " " << v[l] << endl;
}

Measured memory_bytes: 1208
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long ll;

const int N=155;

int n,L,Mo;
int f[N][N],g[N][N][N];

void inc(int &x,int y) {x=x+y>=Mo?x+y-Mo:x+y;}

int main() {
	scanf("%d%d%d",&n,&L,&Mo);
	if (L&1) {
		g[0][0][0]=1;int m=(L>>1)+((n+1)>>1);
		fo(i,0,m-1) 
			fo(j,0,n>>1) 
				fo(k,0,L+1) {
					inc(g[i+1][0][0],g[i][j][k]);
					if (i<(n>>1)) inc(g[i+1][j+1][0],g[i][j][k]);
					if (i>=(L>>1)) inc(g[i+1][0][k?k+1:0],g[i][j][k]);
					if (i>=(L>>1)&&i<(n>>1)) inc(g[i+1][j+1][max(j+2,k+1)],g[i][j][k]);
				}
		int ans=0;
		fo(i,0,n>>1) fo(j,0,L+1) inc(ans,g[m][i][j]);
		printf("%d\n",ans);
	} else {
		fo(i,0,n) fo(j,0,i) f[i][j]=0;
		f[0][0]=1;
		fo(i,0,n-1) {
			fo(j,0,min(i,L>>1)) {
				inc(f[i+1][j+1],f[i][j]);
				inc(f[i+1][0],f[i][j]);
			}
		}
		int an_0=0,an_1=0;
		fo(j,0,L>>1) {
			inc(an_0,f[n>>1][j]);
			inc(an_1,f[(n+1)>>1][j]);
		}
		printf("%d\n",(ll)an_0*an_1%Mo);
	}
	return 0;
}

Measured memory_bytes: 13568
/**
*    created: 27.06.2020 21:00:40
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long
#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++)
#define all(x) (x).begin(),(x).end()
#define pcnt(bit) __builtin_popcountll(bit)
#define mod 1000000007
#define pi acos(-1.0)
using namespace std;
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) {if (b < a) {a = b; return 1;} return 0;}

signed main() {

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

    string s, t;
    cin >> s >> t;
    int n = s.size();
    int cnt = 0;
    rep(i,n) if (s[i] != t[i]) cnt++;
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3800
N, M = [int(e) for e in input().split(" ")]
ABs = []
for _ in range(N):
    ABs.append([int(e) for e in input().split(" ")])

ABs = list(sorted(ABs))
# print(ABs)
count = M
memMoney = 0
for a,b in ABs:
    if count - b > 0:
        memMoney = memMoney + a*b
        count = count - b
        continue

    if count - b == 0:
        memMoney = memMoney + a*b
        count = count - b
        break

    d = count
    memMoney = memMoney + a*d
    count = count - d
    break

print(memMoney)


Measured memory_bytes: 22752
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    #D - 3N Numbers
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    l=[0]*(N+1)
    q=[A[i] for i in range(N)]
    tot=sum(q)
    heapify(q)

    l[0]=tot
    for i in range(0,N):
        a=A[N+i]
        if a>q[0]:
            tot+=a-q[0]
            heappop(q)
            heappush(q,a)
        l[i+1]=tot

    l2=[0]*(N+1)
    q=[-A[i] for i in range(2*N,3*N)]
    tot=-sum(q)
    heapify(q)
    l2[0]=tot

    for i in range(0,N):
        a=A[-N-i-1]
        if a<-q[0]:
            tot+=a-(-q[0])
            heappop(q)
            heappush(q,-a)
        l2[i+1]=tot
    ans=-float('inf')

    for i in range(N+1):
        ans=max(l[i]-l2[-1-i],ans)
    print(ans)
    #printe(l,l2)



if __name__ == "__main__":
    main()

Measured memory_bytes: 123652
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18+69;
int n, m, s;
vector<pair<int, pair<int, ll> > >adj[55];
pair<ll, ll>cd[55];
ll dist[55][5005];
bool cmp(pair<ll, pair<ll, int> >a, pair<ll, pair<ll, int> >b){
	if(a.first==b.first) return a.second.first>b.second.first;
	return a.first>b.first;
}
int main(){
	cin>>n>>m>>s;
	for(int i=0; i<m; i++){
		int u, v, a; ll b; cin>>u>>v>>a>>b;
		adj[u].push_back({v,{a,b}});
		adj[v].push_back({u,{a,b}});
	}
	if(s>=5005) s=5004;
	for(int i=1; i<=n; i++)
		cin>>cd[i].first>>cd[i].second;
	priority_queue<pair<ll, pair<ll, int> >, vector<pair<ll, pair<ll, int> > >, function<bool(pair<ll, pair<ll, int> >, pair<ll, pair<ll, int> >)> >pq(cmp);
	for(int i=1; i<=n; i++)
		for(int j=0; j<5005; j++)
			dist[i][j]=inf;
	dist[1][s]=0ll;
	pq.push({0,{s,1}});
	for(;!pq.empty();){
		ll d=pq.top().first, sc=pq.top().second.first, nw=pq.top().second.second;
		pq.pop();
		if(dist[nw][sc]>d) continue;
		if(sc+cd[nw].first<5005 && dist[nw][sc+cd[nw].first]>dist[nw][sc]+cd[nw].second){
			dist[nw][sc+cd[nw].first]=dist[nw][sc]+cd[nw].second;
			pq.push({dist[nw][sc+cd[nw].first], {sc+cd[nw].first, nw}});
		}
		for(auto i:adj[nw]){
			int nx=i.first, cst=i.second.first; ll tm=i.second.second;
			if(sc<cst) continue;
			if(dist[nx][sc-cst]>dist[nw][sc]+tm){
				dist[nx][sc-cst]=dist[nw][sc]+tm;
				pq.push({dist[nx][sc-cst], {sc-cst, nx}});
			}
		}
	}
	for(int i=2; i<=n; i++){
		ll ans=inf;
		for(int j=0; j<5005; j++)
			ans=min(ans, dist[i][j]);
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 11368
//Author ::  ABHINAV3010 ::

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fast ios_base::sync_with_stdio(false)
typedef long long ll;
typedef pair<ll,ll> p;
ll mod=1000000007;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
ll power(ll x, ll y, ll p=mod)
{ll res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1;x = (x*x) % p;}return res;}
int main()
{
fast;
ll l;
cin>>l;
double x=l/3.0;
double y=l/3.0;
double z=l/3.0;
double ans=x*y*z;
cout<<fixed<<setprecision(10)<<ans<<endl;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k,c=0;
  cin>>n>>k;
  int b[n+1]={};
  for(int i=0;i<k;i++)
  {
    int d;
    cin>>d;
    int a[d];
    for(int i=0;i<d;i++)
    {
      cin>>a[d];
      b[a[d]]=1;
    }
  } 
  for(int i=1;i<n+1;i++)
  {
    if(b[i]==0)
      c++;
  }
  cout<<c;
  return 0;
  
}

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

int main(){
    long long N,K;
    cin>>N>>K;
    if(N>=K){
        long long l=N%K;
        long c=K-l;
        if(c<=l)cout<<c;
        else cout<<l;
    }
    else{
      long long p=K-N;
      long long d=K-p;
      if(d<=p)cout<<d;
      else cout<<p;  
    } 
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep0(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define rrep(i,n) for (int i=(int)(n)-1; i>=0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

template<typename T> struct is_pair : false_type{};
template<typename T1, typename T2> struct is_pair<pair<T1, T2>> : true_type{};
template<typename T> struct is_vector : false_type{};
template<typename T> struct is_vector<vector<T>> : true_type{};

template<typename T1, typename T2>
istream &operator >> (istream &istr, pair<T1, T2> &p) {
  istr >> p.first >> p.second;
  return istr;
} 
template<typename T1, typename T2>
ostream &operator << (ostream &ostr, const pair<T1, T2> &p) {
  ostr << p.first << " " << p.second;
  return ostr;
}
template<typename T>
ostream &operator << (ostream &ostr, const vector<T> &vec) {
  if (vec.empty()) return ostr;
  bool vp = is_vector<T>() || is_pair<T>();
  ostr << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) {
    ostr << (vp ? "\n" : " ") << *itr;
  }
  return ostr;
}

template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int modpow(int a, long long n, int mod = MOD) {
  int ret = 1;
  do {
    if (n & 1) ret = 1LL * ret * a % mod;
    a = 1LL * a * a % mod;
  } while (n >>= 1);
  return ret;
}

template<typename T>
T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<typename T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

template<typename T1, typename T2>
bool CompareBySecond(pair<T1, T2> a, pair<T1, T2> b) {
  return a.second != b.second ? a.second < b.second : a.first < b.first;
}
template<typename T>
bool CompareBySlope(pair<T, T> a, pair<T, T> b) {
// counterclockwise from 12 o'clock direction
  if (a.first * b.first < 0) return a.first < b.first;
  if (a.first == 0) return a.second >= 0 || b.first > 0;
  if (b.first == 0) return b.second < 0 && a.first < 0;
  return a.second * b.first < a.first * b.second;
}


/* -------- <templates end> -------- */


void solve() {
  int h, n; cin >> h >> n;
  vi arr(n);
  rep(i,n) cin >> arr[i];
  if (accumulate(ALL(arr), 0LL) >= h) cout << "Yes\n";
  else cout << "No\n";
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main()
{
    unsigned int a_undelic = 0, b_delic = 0, c_delicp = 0;
    unsigned int tmp_cookie = 0, total = 0;

    scanf("%d %d %d", &a_undelic, &b_delic, &c_delicp);
    total = c_delicp + b_delic;

    if ((b_delic + a_undelic) >= c_delicp) {
        total -= tmp_cookie;
    } else {
    	tmp_cookie = c_delicp - b_delic;
    	tmp_cookie -= a_undelic + 1;
    	total -= tmp_cookie;
    }
	printf("%d\n",total);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>

using namespace std;

int main() {
	int i, j,k;	//i??????j????¨?
	int n, m, l;	//a=n*m????????????b=m*l??????
	int a[100][100], b[100][100],c,cc;
	long C[100][100];

	cin >>n>>m>>l;

	for (i = 0; i < 100; i++) {
		for (j = 0; j < 100; j++) {
			a[i][j] = 0;
			b[i][j] = 0;
			C[i][j] = 0;
		}
	}

	//??????A
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	
	//??????B
	for (i = 0; i < m; i++) {
		for (j = 0; j < l; j++) {
			cin >> b[i][j];
		}
	}

	//??????C
	for (i = 0; i < n; i++) {
		for (j = 0; j < l; j++) {
			for (k = 0; k <m; k++) {
				C[i][j] += a[i][k] * b[k][j];
			}
			cout << C[i][j];
			if (j != l - 1)cout << " ";
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1316
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long double n,d,x;
int main()
{
	cin>>n>>d>>x;
	long double ans=0,sum=2*n*d+n*(2*n-1)*x;
	for(int i=n;i>0;--i){
		ans+=(2*d+(2*n-1)*x)/2;
		sum-=(2*d+(2*n-1)*x)/n;
		d=(2*d+5*x+2*n*d)/2/n;
		--n;
		x=(sum-2*n*d)/n/(2*n-1);
	}
	printf("%.15lf\n",(double)ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const long long INF = 100000000;
const long long MOD = 1000000007;


long long gcd(long long a,long long b){
  if(a<b){
    swap(a, b);
  }
  if(a%b==0)
    return b;
  return gcd(a % b, b);
}

int main()
{
  int N;
  cin >> N;
  set<int> set;
  for (int i = 0; i < N; i++)
  {
    int a;
    cin >> a;
    set.insert(a);
  }

  if((N-(int)set.size())%2==0){
    cout << (int)set.size() << endl;
  }
  else
    cout << (int)set.size() -1<< endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
std::vector<std::pair<int,int>> g[1 + nmax];
int sz[1 + nmax];
ll level[1 + nmax];

void dfs(int node, int parent, ll acc) {
  sz[node] = 1;
  level[node] = acc;
  for(int h = 0;h < g[node].size(); h++) {
    int to = g[node][h].first;
    if(to != parent) {
      dfs(to, node, acc + g[node][h].second);
      sz[node] += sz[to];
    }
  }
}

int solve(int node, int parent, int target) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h].first;
    if(to != parent && target <= sz[to])
      return solve(to, node, target);
  }
  return node;
}

int main() {
  int n;
  std::cin >> n;
  for(int i = 1;i < n; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    g[x].push_back({y, cost});
    g[y].push_back({x, cost});
  }
  dfs(1, 0, 0);
  int centroid = solve(1, 0, (n + 1) / 2), centroid2;
  centroid2 = centroid;
  dfs(centroid, 0, 0);

  for(int h = 0; h < g[centroid].size(); h++) {
    int to = g[centroid][h].first;
    if(sz[to] == (n + 1) / 2)
      centroid2 = to;
  }

  ll result = 0;
  if(centroid != centroid2) {
    for(int i = 1;i <= n; i++)
      result += level[i] * 2;
    std::cout << result - level[centroid2];
  } else {
    for(int i = 1;i <= n; i++)
      result += level[i] * 2;
    ll smin = 1000000000;

    for(int h = 0; h < g[centroid].size(); h++) {
      int to = g[centroid][h].first;
      smin = std::min(smin, level[to]);
    }
    result -= smin;
    std::cout << result;
  }
  return 0;
}


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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rept(i,k,n) for(ll i = (k); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<long long,long long> Pll;
typedef tuple<int,int,int> Tii;



int main(){
    int n,k;
    cin>>n>>k;
    vector<int> p(n);
    rep(i,n) cin>>p[i];
    Sort(p);
    int sum=0;
    rep(i,k) sum+=p[i];
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 3600
N=int(input())
T=list(map(int,input().split()))
M=int(input())
for i in range (M):
	ans=0
	P,X=map(int,input().split())
	for j in range (N):
		if j==P-1:
			ans+=X
		else:
			ans+=T[j]
	print(ans)

Measured memory_bytes: 3060
#include<cstdio>
#include<algorithm>
using namespace std;
int K, n;
struct point {
	long long x, y;
	bool operator<(const point &p)const {
		if (x < p.x) {
			return (p.y - y) >= (p.x - x) * K;
		}
		else {
			return (y - p.y) < (x - p.x) * K;
		}
	}
}w[201000];
int BIT[201000];
void Add(int a) {
	while (a <= n) {
		BIT[a]++;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}
int main() {
	int i, a;
	scanf("%d%d", &n, &K);
	w[1] = { 1,0 };
	for (i = 1; i <= n; i++) {
		scanf("%d", &a);
		w[i+1] = { i+1,w[i].y + a };
	}
	n++;
	sort(w+1, w + n+1);
	long long res = 0;
	for (i = 1; i <= n; i++) {
		int x = w[i].x;
		res += n - x + 1 - (i - Sum(x));
		Add(x);
	}
	printf("%lld\n", res);
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <math.h>
#include <numeric>
using namespace std;

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef vector<int> vi;

template<class T>
inline bool ChangeMin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

    vi W(N);
    REP(i, N) {
        cin >> W[i];
    }

    int s1 = 0, s2 = 0, diff_min = 10001;
    REP(i, N-1) {
        s1 = accumulate(W.begin(), W.begin()+(i+1), 0);
        s2 = accumulate(W.begin()+(i+1), W.end(), 0);
        ChangeMin(diff_min, abs(s1-s2));
    }

    cout << diff_min << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
int main(){
    int n;
    cin >> n;
    long double x[n],y[n];
    rep(i,n) cin >> x[i] >> y[i];
    long double hoge = 1;
    rep(i,n-1) hoge*=(i+1);
    long double ans = 0;
    for(int i = 0;i<n-1;i++){
        for(int j = i+1;j<n;j++){
            ans+=sqrt((y[j]-y[i])*(y[j]-y[i])+(x[j]-x[i])*(x[j]-x[i]));
        }
    }
    ans = 2*ans/n;
    cout << setprecision(20) << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    static int N;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = Integer.parseInt(sc.next());
        sc.close();
        System.out.println(dfs(0,false,false,false));

    }

    static private int dfs(int n, boolean hasThree, boolean hasFive, boolean hasSeven){
      int res = 0;
      if(n > N) return res;

      if(n <= N && n != 0 && hasThree && hasFive && hasSeven) res++;

      if(n >= Math.pow(10, 8)) return res;

      res += dfs(n * 10 + 3, true, hasFive, hasSeven);
      res += dfs(n * 10 + 5, hasThree, true, hasSeven);
      res += dfs(n * 10 + 7, hasThree, hasFive, true);
      return res;
    }
}


Measured memory_bytes: 23252
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main(){
    long long x, cnt = 0, digit = 0;
    cin >> x;
    digit = log10(x)+1;
    cnt = pow(10,digit-1);
    long long loop = x % cnt;
    long long diff = 1;
    long long max = 0;
    long long tmp = x;
    //cout << cnt << " " << loop << " " << tmp << " " << loop - tmp <<  endl;
    while(tmp){
        max += tmp % 10;
        tmp /= 10;
    }
    for(int i = 0; i <= digit - 1; i++){
        cnt = pow(10,i);
        loop = x % cnt;
        tmp = x - (loop+1);
        long long max_tmp = 0;
        if(x >= 10){
            while(tmp){
                max_tmp += tmp % 10;
                tmp /= 10;
            }
            if(max_tmp > max){
                max = max_tmp;
            }
        }else{
            max = x;
        }
        //cout << "cnt = " << cnt << ",loop = " << loop << ",tmp = " << x-(loop+1) << ",max_tmp = " << max_tmp <<  endl;
    }
    cout << max << endl;
}

Measured memory_bytes: 256
<?php
fscanf(STDIN,"%d",$n);
$a_li = explode(" ",trim(fgets(STDIN)));

$sum = 0;
array_unshift($a_li,0);
for($j=0;$j<$n;$j++){
    $sum += abs($a_li[$j+1]-$a_li[$j]);
}
$sum += abs($a_li[$n]);

for($i=1;$i<=$n;$i++){
  $remove = abs($a_li[$i]-$a_li[$i-1])+abs($a_li[$i+1]-$a_li[$i]);
  $add = abs($a_li[$i+1]-$a_li[$i-1]);
  echo ($sum-$remove+$add)."\n";
}


Measured memory_bytes: 25932
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int main()
{
	cin>>a>>b>>c;
	if(a==b) d++;
	if(a==c) d++;
	if(b==c) d++;
	if(d==1) cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main()
{
    string S; cin >> S;
    int w; cin >> w;
    for (int i = 0; i < S.size(); i += w) {
        cout << S[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
# Aizu Problem NTL_1_B: Power
#
import itertools
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")

m, n = [int(_) for _ in input().split()]
mod = 1000000007
print(pow(m, n, mod))

Measured memory_bytes: 7860
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;
typedef long long ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

void Main() {
  Cin(string, s, t);
  bool ok = false;
  for (int i = 0; i < sz(s); ++i) {
    if (s == t) ok = true;
    string back = {s.back()};
    s = back + s.substr(0, sz(s) - 1);
  }
  puts(ok ? "Yes" : "No");
  return;
}

int main() {
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cassert>
typedef long long int ll;
using namespace std;

ll follow(auto& nbr, ll x1, ll x2, ll gA, ll gB) {
  while (1) {
    // fprintf(stderr, "(%lld, %lld)\n", x1, x2);
    if (x2 == gA)  return 0;
    if (x2 == gB)  return 1;
    auto lst = nbr.at(x2);
    assert(lst.size() == 2);
    if (lst.at(0) == x1) {
      x1 = x2;
      x2 = lst.at(1);
    }else {
      assert(lst.at(1) == x1);
      x1 = x2;
      x2 = lst.at(0);
    }
  }
}

string chk(ll n, auto& nbr) {
  ll six = 0;
  ll four = 0;
  ll fourA = 0;
  ll fourB = 0;
  for (ll i = 1; i <= n; i++) {
    ll k = nbr.at(i).size();
    if (k % 2 == 1)  return "No";
    if (k >= 6)  six++;
    if (k == 4)  {
      four++;
      if (four == 1)       fourA = i;
      else if (four == 2)  fourB = i;
    }
  }
  if (six >= 1)   return "Yes";
  if (four >= 3)  return "Yes";
  if (four <= 1)  return "No";
  ll count = 0;
  for (auto x : nbr.at(fourA)) {
    count += follow(nbr, fourA, x, fourA, fourB);
  }
  return count == 2 ? "Yes" : "No";
}

int main() {
  ll n, m;
  cin >> n >> m;
  vector< vector<ll> > nbr(n+1);
  for (ll i = 0; i < m; i++)  {
    ll a, b;
    cin >> a >> b;
    nbr.at(a).push_back(b);
    nbr.at(b).push_back(a);
  }

  /*
  for (ll i = 1; i <= n; i++) {
    fprintf(stderr, "%lld : ", i);
    for (ll j = 0; j < (ll) nbr.at(i).size(); j++) {
      fprintf(stderr, "%lld ", nbr.at(i).at(j));
    }
    fprintf(stderr, "\n");
  }
  */

  cout << chk(n, nbr) << endl;
  return 0;
}


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

using namespace std;


int main()
{
    string s;
    int a=0,b=0;
    cin>>s;
    for(int i=0;i<=2;i++)
    {
        if(s[i]=='A')a++;
        else b++;
    }
    if(a>0 && b>0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;



    return 0;
}


Measured memory_bytes: 256
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
s = [_ for _ in input()]

cnt=0
for i in range(n-2):
  if ''.join(s[i:i+3])=='ABC':
    cnt+=1

print(cnt)

Measured memory_bytes: 38384
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}
func test(flags uint64, i uint64) bool {
	return (flags & (1 << i)) != 0
}
func set(flags uint64, i uint64) uint64 {
	return flags | (1 << i)
}
func clear(flags uint64, i uint64) uint64 {
	return flags & ^(1 << i)
}
func flip(flags uint64, i uint64) uint64 {
	return flags ^ (1 << i)
}
func all(flags uint64) bool {
	return flags == math.MaxUint64
}
func any(flags uint64) bool {
	return flags != 0
}
func none(flags uint64) bool {
	return flags == 0
}
func count(flags uint64) uint64 {
	cnt := uint64(0)
	for i := 0; i < 64; i++ {
		if (flags & (1 << uint64(i))) != 0 {
			cnt++
		}
	}
	return cnt
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	q := nextInt(sc)
	wtr := bufio.NewWriter(os.Stdout)
	var flags uint64
	for i := 0; i < q; i++ {
		op := nextInt(sc)
		if op == 0 || op == 1 || op == 2 || op == 3 {
			x := uint64(nextInt(sc))
			if op == 0 {
				if test(flags, x) {
					fmt.Fprintln(wtr, 1)
				} else {
					fmt.Fprintln(wtr, 0)
				}
			} else if op == 1 {
				flags = set(flags, x)
			} else if op == 2 {
				flags = clear(flags, x)
			} else {
				flags = flip(flags, x)
			}
		} else if op == 4 {
			if all(flags) {
				fmt.Fprintln(wtr, 1)
			} else {
				fmt.Fprintln(wtr, 0)
			}
		} else if op == 5 {
			if any(flags) {
				fmt.Fprintln(wtr, 1)
			} else {
				fmt.Fprintln(wtr, 0)
			}
		} else if op == 6 {
			if none(flags) {
				fmt.Fprintln(wtr, 1)
			} else {
				fmt.Fprintln(wtr, 0)
			}
		} else if op == 7 {
			fmt.Fprintln(wtr, count(flags))
		} else {
			fmt.Fprintln(wtr, flags)
		}
	}
	wtr.Flush()
}



Measured memory_bytes: 3212
#include<bits/stdc++.h>
using namespace std;
//D問題

int main(){
    long long a,b,n;
    cin >> a >> b>> n;
    if(b == 1){
        cout << 0 << endl;
    }else if(n<b-1){
        long long x = a*n/b;
        long long y = n/b;   
        cout << x << endl;
    }else if(n>=b-1){
        long long x = a*(b-1)/b;
        long long y = (b-1)/b;
        cout << x << endl;
    }
    return 0;
}


Measured memory_bytes: 3632