akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define rep(i,j,n) for(int i=j; i<n; i++)
#define INF 1000000000000000000 // If you use it, make sure not to put in "int" type variable ;(, use long long int
void optimizeIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
const ll mod=1000000007;
 
int main()
{
    optimizeIO();
    int nT; nT=1;
	while(nT--)
	{
		ll n; cin>>n;
		ll a[n], b[n-1]; 
		rep(i,0,n-1) cin>>b[i];
		a[0]=b[0];
		a[n-1]=b[n-2];
		for(int i=n-2; i>=1; i--)
		{
			a[i]=min(b[i],b[i-1]);
		}
		ll ans=0;
		rep(i,0,n) ans+=a[i];
		cout<<ans;
	}
	return 0;
}

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

const int MAX = 2000005;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

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

ll COM(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main(){
    int x, y;
    cin >> x >> y;
    if((2*x-y)%3 != 0 || (2*y-x)%3 != 0){
        cout << 0 << endl;
    }
    else{
        COMinit();
        ll n = (x+y)/3, k = (2*x-y)/3;
        cout << COM(n, k) << endl;
    }
}

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

namespace CsTest
{
    public class Program
    {
        public class Comparer : IComparer<int[]>
        {
            public int Compare(int[] x, int[] y)
                => x[1] - y[1];
        }

        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine().Trim());
            int[][] works = new int[N][];
            for (int i = 0; i < N; ++i)
            {
                works[i] = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            }

            Array.Sort(works, new Comparer());

            int time = works[works.Length - 1][1];
            for (int i = works.Length - 1; i >= 0; --i)
            {
                time = Math.Min(works[i][1], time);
                time -= works[i][0];
                if (time < 0)
                {
                    Console.WriteLine("No");
                    return;
                }
            }
            Console.WriteLine("Yes");
        }
    }
}

Measured memory_bytes: 28560
#include <stdio.h>
#include <math.h>

#define calc(v, n, p, pr)	(((p) * ((v) / (n) * (n)) * (pr)) + ((p) * ((v) % (n))))

int minv;
int g;
int ap[32] = {0, 380}, bp[32] = {0, 550}, cp[32] = {0, 850};

void dfs(int a, int b, int c)
{
	int mg = a * 200 + b * 300 + c * 500;
	int price = ap[a] + bp[b] + cp[c];
	if (mg == g){
		minv = fmin(price, minv);
		return;
	}
	if (mg > g) return;
	if (price > minv) return;

	dfs(a + 1, b, c);
	dfs(a, b + 1, c);
	dfs(a, b, c + 1);
}

int main(void)
{
	int i;


	for (i = 2; i <= 25; i++){
		ap[i] = calc(i, 5, ap[1], 0.8);
		bp[i] = calc(i, 4, bp[1], 0.85);
		cp[i] = calc(i, 3, cp[1], 0.88);
	}

	while (scanf("%d", &g), g){
		minv = 1e6;
		dfs(0, 0, 0);
		printf("%d\n", minv);
	}
	return (0);
}

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

using namespace std;

int N;
long long int x, a[2050];
long long int cost[2050][2050];

int main(void) {

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

	int I = -1;
	long long int tmp = 100000000000;
	for (int i = 0; i < N; i++) {
		if (a[i] < tmp) { tmp = a[i]; I = i; }
	}

	for (int i = 0; i < N; i++) { cost[i][0] = a[i]; }
	
		for (int X = 1; X <= N; X++) {
			for(int i=0;i<N;i++){
			cost[i][X] = min(cost[i][X - 1], cost[(i + N - 1) % N][X - 1]);
		}
	}


	for (int X = 0; X <= 3; X++) {
		for (int i = 0; i < N; i++) {
			//cout << "cost[" << i << "][" << X << "]= " << cost[i][X] << endl;
		}
	}
	long long int ans = 200000000000034;

	for (int X = 0; X <= N; X++) {
		long long int tmp = 0;
		for (int i = 0; i < N; i++) {
			tmp += cost[i][X];
		}
		tmp += X*x;
		//cout << "tmp= " << tmp << endl;
		ans = min(ans, tmp);
	}

	cout << ans << endl;

	//system("pause");
	return 0;
}

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


int main()
{
	//#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	//#endif
	
	//int t;
	//cin>>t;
	//while(t--)
	{
		int n,w;
		cin>>n>>w;
		int a[n][2];
		for(int i=0;i<n;i++)
		{
			cin>>a[i][0]>>a[i][1];
		}
		ll dp[w+1];
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++)
		{
			for(int j=w;j>=0;j--)
			{
				if(j-a[i][0]>=0)
				{
					dp[j]=max(dp[j],dp[j-a[i][0]]+a[i][1]);
				}
			}
		}
		cout<<dp[w]<<'\n';
		
	}
		
}


Measured memory_bytes: 4380
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int main(){
  string s,t;
  cin >> s >> t;
  vector<int> vs;
  vector<int> vt;
  for(int i = 0; i < (int)s.length(); i++){
    vs.push_back(s[i]);
  }
  for(int j = 0; j < (int)t.length(); j++){
    vt.push_back(t[j]);
  }
  sort(vs.begin(), vs.end());
  sort(vt.begin(), vt.end(), greater<int>());

  for(int i=0; i < min(s.length(),t.length()); i++){
    if(vs[i]>vt[i]){
      cout << "No" << endl;
      return 0;
    }
    if(vs[i]<vt[i]){
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(s.length()<t.length()){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n, m, c = map(int, input().split())
b = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(n)]

cc = 0
for v in l:
    t = c
    for vv in zip(b, v):
        t += vv[0] * vv[1]

    if t > 0:
        cc += 1
    
print(cc)

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

int main() {
    // input
    int A, B, C;
    cin >> A >> B >> C;

    // solve
    bool flag = false;
    int sum = 0;
    for (int i = 1; i <= B; ++i) {
        sum += A;
        if (sum % B == C) {
            flag = true;
            break;
        }
    }

    // output
    cout << (flag ? "YES" : "NO") << endl;

    return 0;
}


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

const int INF = 1001001001;

int main() {
    int n, m;
    cin >> n >> m;

    vector<P> v;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        v.push_back({b, a});
    }

    sort(v.begin(), v.end());

    // rep(i, m) {
    //     cout << "i: " << i << " f: " << v[i].first << " s: " << v[i].second << endl; 
    // }
    // cout << endl;

    int ans = 0;
    int t = 1;
    rep(i, m) {
        if (t <= v[i].second) {
            // cout << "i: " << i << " " << v[i].first << " x " <<v[i].second << endl;
            ans++;
            t = v[i].first;
        }
    }

    cout << ans << endl;

    return 0;
}

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

if n >= 1800:
  print("1")
elif n >= 1600:
  print("2")
elif n >= 1400:
  print("3")
elif n >= 1200:
  print("4")
elif n >= 1000:
  print("5")
elif n >= 800:
  print("6")
elif n >= 600:
  print("7")
elif n >= 400:
  print("8")

Measured memory_bytes: 9092
//#include<iostream>
//using namespace std;
//int main()
//{
//	// 入力 n:人数 k:必殺技の回数
//	uint32_t n, k;
//
//	cin >> n >> k;
//
//	// 敵のHPの配列
//	long long h[2 * 10 ^ 5];
//
//	// 攻撃の回数を求めよ
//
//	for (uint32_t i = 0; i < n; ++i) {
//		cin >> h[i];
//	}
//
//	// ソート (大きい順番)
//	for (uint32_t i = 0; i < n; ++i) {
//		for (uint32_t j = 0; j < n - 1; ++j) {
//			if (h[j] < h[j + 1]) {
//				swap(h[j], h[j + 1]);
//			}
//		}
//	}
//
//	long long sum = 0;
//	for (uint32_t i = k; i < n; ++i) {
//		sum += h[i];
//	}
//
//	cout << sum << endl;
//	return 0;
//}

#include<iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
	// 入力 n:人数 k:必殺技の回数
	uint32_t n, k;

	cin >> n >> k;

	// 敵のHPの配列
	vector<long long> h;
	//long long h[2 * 10 ^ 5];

	// 攻撃の回数を求めよ

	for (uint32_t i = 0; i < n; ++i) {
		h.push_back(0);
		cin >> h[i];
	}

	//// ソート (大きい順番)
	//for (uint32_t i = 0; i < n; ++i) {
	//	for (uint32_t j = 0; j < n - 1; ++j) {
	//		if (h[j] < h[j + 1]) {
	//			swap(h[j], h[j + 1]);
	//		}
	//	}
	//}

	std::sort(h.begin(), h.end(), std::greater<long long>());

	long long sum = 0;
	for (uint32_t i = k; i < n; ++i) {
		sum += h[i];
	}

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 2420
//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
signed main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = min(b,d) - max(a, c);
    if(ans<0) ans = 0;
    cout << ans << endl;
    return 0;
}
 

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from sys import stdin
import heapq
# import numpy as np
import sys
sys.setrecursionlimit(10**6)


s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

X, Y, Z, K = ds_in()
A_list = ds_in()
B_list = ds_in()
C_list = ds_in()

A_list.sort(reverse=True)
B_list.sort(reverse=True)
C_list.sort(reverse=True)


def search(cand, searched):
    if len(searched) > K-1:
        exit()
    current = searched[-1][1]
    cand1 = (current[0]+1, current[1], current[2])
    cand2 = (current[0], current[1]+1, current[2])
    cand3 = (current[0], current[1], current[2]+1)
    if cand1[0] < len(A_list):
        val = A_list[cand1[0]] + B_list[cand1[1]] + C_list[cand1[2]]
        if (-val, cand1) not in cand:
            heapq.heappush(cand, (-val, cand1))
    if cand2[1] < len(B_list):
        val = A_list[cand2[0]] + B_list[cand2[1]] + C_list[cand2[2]]
        if (-val, cand2) not in cand:
            heapq.heappush(cand, (-val, cand2))
    if cand3[2] < len(C_list):
        val = A_list[cand3[0]] + B_list[cand3[1]] + C_list[cand3[2]]
        if (-val, cand3) not in cand:
            heapq.heappush(cand, (-val, cand3))
    next_ = heapq.heappop(cand)
    print(-next_[0])
    searched.append(next_)
    # print('cand', cand)
    # print('searched', searched)
    search(cand=cand, searched=searched)


searched = [(-(A_list[0] + B_list[0] + C_list[0]), (0, 0, 0))]
cand = []
print(-searched[0][0])
search(cand=cand, searched=searched)




Measured memory_bytes: 8296
#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 n; cin>>n;
  string s; cin>>s;
  int ans=1;
  rep(i,s.size()-1) if(s.at(i+1)!=s.at(i)) ans++;
  cout<<ans<<endl;
}

Measured memory_bytes: 512
n, m = (int(i) for i in input().split())  
x = sorted([int(i) for i in input().split()])

if m > 1:
    x_diff = []
    for i in range(m-1):
        x_diff.append(x[i+1] - x[i])
else:
    x_diff = [0]

if n > 1:
    x_diff = sorted(x_diff)[:-(n-1)]

print(sum(x_diff))

Measured memory_bytes: 13832
#include <stdio.h>

#define MAX 500000
#define S 2000000000

void merge (int *, int, int, int, int);
void mergeSort (int *, int, int, int);

int l[MAX/2+2], r[MAX/2+2];
int count;

int main() {
  int a[MAX], n, i;

  count = 0;
  scanf("%d", &n);
  for(i = 0 ; i < n ; i++) {
    scanf("%d", &a[i]);
  }

  mergeSort(a, n, 0, n);

  for(i = 0 ; i < n ; i++) {
    printf("%d", a[i]);
    if(i != n-1) printf(" ");
  }
  printf("\n%d\n", count);

  return 0;
}

void merge(int *a, int n, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  int i, j, k;
  
  for(i = 0 ; i < n1 ; i++) {
    l[i] = a[left + i];
  }
  for(i = 0 ; i < n2 ; i++) {
    r[i] = a[mid + i];
  }
  l[n1] = S;
  r[n2] = S;
  for (k = left, i = 0, j = 0; k < right ; k++) {
    count++;
    if(l[i] <= r[j]) {
      a[k] = l[i++];
    }
    else {
      a[k] = r[j++];
    }
  }
}

void mergeSort(int *a, int n, int left, int right){
  int mid;
  
  if(left+1 < right){
    mid = (left + right) / 2;
    mergeSort(a, n, left, mid);
    mergeSort(a, n, mid, right);
    merge(a, n, left, mid, right);
  }
}

Measured memory_bytes: 4508
import sys
n = int(input())
cnt = 1
li=['']*n
for i in range(n):
    li[i] = input()
li.sort()
for i in range(n):
    if (i + 1 == n):
        break
    if (li[i] == li[i + 1]):
        continue
    cnt+=1
print(cnt)

Measured memory_bytes: 23932
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string less = "LESS",greater="GREATER",equal="EQUAL";
  
  string A,B;
  cin>>A>>B;
  string ans;
  if(A.size()<B.size()){
    ans=less;
  }
  else if(A.size()>B.size()){
    ans=greater;
  }
  else{
    ans=(A>B)? greater:(A<B)? less:equal;
  }
  cout<<ans;
}

Measured memory_bytes: 256
import sys
from itertools import accumulate
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
counter = M

d = []
d2 = []
for i in range(N):
    d.append([0] * N)
for i in range(N):
    d2.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        d[L-1][R-1] += 1
#        for i in range(L):
#            for j in range(N - R + 1):
#                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
#            print(d)
            for i in range(N):
                d[i] = d[i][::-1]
#            print(d)
            for i in range(N):
                if i == 0:
                    d[N-1] = list(accumulate(d[N-1][::-1]))[::-1]
                else:
                    for j in range(N):
                        if j == 0:
                            temp = d[N-1-i][N-1-j]
                        else:
                            temp += d[N-1-i][N-1-j]
                        d[N-1-i][N-1-j] = d[N-i][N-1-j] + temp
#            print(d)
#            for x in d:
#                print(x)
            flag = True
    else:
        print(d[L-1][N-R])


Measured memory_bytes: 60892
#include<iostream>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  int counter = 0;
  if (a[0] == '1') ++ counter;
  if (a[1] == '1') ++ counter;
  if (a[2] == '1') ++ counter;
  cout << counter << endl;
}

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

using namespace std;

struct Node
{
    int parent;
    int left;
    int right;

    Node() : parent(-1), left(-1), right(-1) {}
};

enum NodeType
{
    Root,
    Internal,
    Leaf,
};

int sibling(vector<Node>& T, int id)
{
    int parent = T[id].parent;
    if (parent == -1)
        return -1;
    else if (T[parent].left == id)
        return T[parent].right;
    else
        return T[parent].left;
}

int degree(vector<Node>& T, int id)
{
    int count = 0;

    if (T[id].left != -1)
        ++count;
    if (T[id].right != -1)
        ++count;

    return count;
}

int depth(vector<Node>& T, int id)
{
    int node = id;
    int count = 0;
    while (T[node].parent != -1) {
        node = T[node].parent;
        ++count;
    }
    return count;
}

int down(vector<Node>& T, int id, int count)
{
    if (id == -1)
        return count-1; // must minus because we -1 means there are no nodes, so we don't count this level

    int left = down(T, T[id].left, count+1);
    int right = down(T, T[id].right, count+1);
    return max(left, right);
}

int height(vector<Node>& T, int id)
{
    return down(T, id, 0);
}

NodeType node_type(vector<Node>& T, int id)
{
    if (T[id].parent == -1)
        return Root;
    else if (T[id].left == -1 && T[id].right == -1)
        return Leaf;
    else
        return Internal;
}

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

    vector<Node> T(n);
    for (int i = 0; i < n; ++i) {
        int id;
        cin >> id;
        cin >> T[id].left >> T[id].right;

        if (T[id].left != -1)
            T[T[id].left].parent = id;
        if (T[id].right != -1)
            T[T[id].right].parent = id;
    }

    // output
    for (int i = 0; i < n; ++i) {
        cout << "node " << i << ": parent = " << T[i].parent;
        cout << ", sibling = " << sibling(T, i);
        cout << ", degree = " << degree(T, i);
        cout << ", depth = " << depth(T, i);
        cout << ", height = " << height(T, i);
        switch (node_type(T, i)) {
            case Root:
                cout << ", root";
                break;
            case Internal:
                cout << ", internal node";
                break;
            case Leaf:
                cout << ", leaf";
                break;
        }
        cout << '\n';
    }
}



Measured memory_bytes: 3104
import os
import os
import sys
from collections import deque

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
VU = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(N + 1)]
for v, u in VU:
    graph[v].append(u)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True
ans = -1
while que:
    v, d = que.popleft()
    if v == T and d % 3 == 0:
        ans = int(d // 3)
    for u in graph[v]:
        if not reached[u, (d + 1) % 3]:
            reached[u, (d + 1) % 3] = True
            que.append((u, d + 1))
print(ans)


Measured memory_bytes: 44256
s = str(input())
k = int(input())
a = []
for i in range(len(s)):
    for j in range(1,k+1):
        if i+j>len(s):
            break
        a.append(s[i:i+j])
a = list(set(a))
a.sort()
print(a[k-1])

Measured memory_bytes: 5068
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    ll N, D, A;
    cin >> N >> D >> A;
    vector<pll> v(N);
    ll x, h;
    for (int i = 0; i < N; i++) {
        cin >> x >> h;
        v[i] = pll(x, h);
    }
    v.push_back(pll(LINF, 0LL));
    sort(v.begin(), v.end());

    vector<ll> sum(N+1);
    ll times = 0;
    for (int i = 0; i < N; i++) {
        x = v[i].first, h = v[i].second;
        h -= sum[i];
        if (h <= 0LL) {
            sum[i+1] += sum[i];
            continue;
        }
        ll mul = (h + A - 1) / A;
        times += mul;
        ll bom = A * mul;
        sum[i] += bom;
        int ind = lower_bound(v.begin(), v.end(),
                    make_pair(x + 2*D + 1, numeric_limits<ll>::min())) - v.begin();
        sum[ind] -= bom;
        sum[i+1] += sum[i];
    }

    cout << times << '\n';
}


Measured memory_bytes: 8576
S=input()

if S.count(S[0])==2:
  if S[0]==S[1]:
    if S.count(S[2])==2:
      print('Yes')
    else:
      print('No')
  else:
    if S.count(S[1])==2:
      print('Yes')
    else:
      print('No')
else:
  print('No')


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;
static const ll MOD = 1000000007;// 1e9 + 7

string s;
ll dp[100001][4] = {};
int main() {
	cin >> s;
	dp[0][0] = 1;
	repe(i, 1, s.size()) {
		ll j = i - 1;
		if (s[j] == 'A') {
			dp[i][1] = dp[i - 1][0] + dp[i - 1][1];

			dp[i][0] = dp[i - 1][0];
			dp[i][2] = dp[i - 1][2];
			dp[i][3] = dp[i - 1][3];
		}
		else if (s[j] == 'B') {
			dp[i][2] = dp[i - 1][1] + dp[i - 1][2];

			dp[i][0] = dp[i - 1][0];
			dp[i][1] = dp[i - 1][1];
			dp[i][3] = dp[i - 1][3];
		}
		else if (s[j] == 'C') {
			dp[i][3] = dp[i - 1][2] + dp[i - 1][3];

			dp[i][0] = dp[i - 1][0];
			dp[i][1] = dp[i - 1][1];
			dp[i][2] = dp[i - 1][2];
		}
		else if (s[j] == '?') {
			dp[i][0] = 3 * dp[i - 1][0] % MOD;
			dp[i][1] += (3 * dp[i - 1][1] + dp[i - 1][0]) % MOD;
			dp[i][2] += (3 * dp[i - 1][2] + dp[i - 1][1]) % MOD;
			dp[i][3] += (3 * dp[i - 1][3] + dp[i - 1][2]) % MOD;;
		}
		dp[i][0] %= MOD;
		dp[i][1] %= MOD;
		dp[i][2] %= MOD;
		dp[i][3] %= MOD;
	}

	cout << dp[s.size()][3] << endl;
	return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

struct UnionFind {
  vector< int > data;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
  }
 
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};


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

  int n,m,k;
  cin >> n >> m >> k;
  UnionFind uf(n);
  vector<pair<int,int>> inp;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    --a;--b;
    uf.unite(a,b);
    inp.pb({a,b});
  }
  vector<ll> ans(n);
  rep(i,n) ans[i] = uf.size(i)-1;
  rep(i,k){
    int c,d;
    cin >> c >> d;
    --c;--d;
    if(uf.find(c) == uf.find(d)){
      ans[c]--;ans[d]--;
    }
  }
  rep(i,m){
    int a = inp[i].first;
    int b = inp[i].second;      
    ans[a]--;ans[b]--;
  }

  rep(i,n)cout << ans[i] << " \n"[i==n-1];
  return 0;
    

}


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

int main(void){
    int x, y;
    
    while(true){
    cin >> x >> y;
    if(!x && !y) return 0;
    
    if(y < x) cout << y << " " << x << endl;
    else cout << x << " " << y << endl;
     }
    
    return 0;
}

Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    long long N,M;
    cin >> N >>M;
    string S,T;
    cin >> S >> T;

    long long l=N*M/__gcd(N,M);
    long long g=__gcd(N,M);
    long long fn=l/N;
    long long fm=l/M;
    long long ans=l;
    for(int i=0;i<g+1;i++){
            if(S[i*fm]!=T[i*fn]){
                ans=-1;
            }
    }
    cout << ans << endl;





}


Measured memory_bytes: 640
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
int n, x;
int a[111111];

int main(void) {
  scanf("%d%d", &n, &x);
  ll res = 0;
  for (int i = 0; i < n; i++) scanf("%d", a+i);
  for (int i = 0; i < n-1; i++) {
    if (a[i]+a[i+1] > x) {
      ll v = (a[i]+a[i+1])-x;
      res += v;
      a[i+1] -= min<ll>(a[i+1], v);
    }
  }
  printf("%lld\n", res);
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n;
  cin >> n;
  vector<int> a(n);
  rep (i, n) cin >> a[i];
  int  mini = INT_MAX;
  lint sum  = 0;
  bool odd  = false;
  rep (i, n) {
    const int x = abs(a[i]);
    sum += x;
    mini = min(mini, x);
    if (a[i] <= 0) odd = !odd;
  }
  cout << (odd ? sum - 2 * mini : sum) << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < n ; i++)
string a[1000];
int b[1000];
int c[1000];
int main(){
	int n,m;
	while( cin >> n >> m && (n||m) ){
		rep(i,n){
			int x,y;
			cin >> a[i] >> x >> y;
			b[i] = y-x+1;
			c[i] = y;
		}
		rep(i,m){
			int x; cin >> x;
			bool f = false;
			rep(j,n){
				if( b[j] <= x && x <= c[j] ){
					cout << a[j] << " " << x-b[j]+1 << endl;
					f = true;break;
				}
			}
			if(!f)cout << "Unknown" << endl;
		}
	}
}

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

bool check(int a) {
  return a >= 1 && a <= 9;
}

int main() {
  int a, b;
  cin >> a >> b;
  if (check(a) && check(b)) {
    cout << a*b;
  } else {
    cout << "-1";
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
char str[100100];
int sum[100100],n;
bool pd(int x){
	return sum[x]-sum[n-x]==x-(n-x)||sum[x]-sum[n-x]==0;
}
int main(){
//	freopen("A.in","r",stdin);
	scanf("%s",str+1);
	n=strlen(str+1);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+str[i]-'0';
	int l=(n+1)/2,r=n,mid;
	if(sum[n]==n||sum[n]==0){
		printf("%d\n",r);
		return 0;
	}
	while(r-l>1){
		mid=(l+r)>>1;
		if(pd(mid)) l=mid;
		else r=mid;
	}
	printf("%d\n",l);
	return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <set>
#include <list>
#include <map>
#include <unordered_map>
#include<queue>


const int INF = 1 << 28;
const long long MOD = 1000000007;
using namespace std;
using Graph = vector<vector<int>>;

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

vector<int> seen(50,-1);
int counter_for_dfs = 0;
void dfs(Graph &G, int v) {
	seen[v] = counter_for_dfs;
	counter_for_dfs++;
	for (auto v_next : G[v]) {
		if (seen[v_next]>=0)continue;

		dfs(G, v_next);
	}
}

void bfs(Graph &G) {
	vector<int> dist(G.size(), -1);
	queue<int> que;
	
	dist[0] = 0;
	que.push(0);
	while (!que.empty()) {
		int v = que.front();
		que.pop();

		for (int g : G[v]) {
			if (dist[g] != -1)continue;
			dist[g] = dist[v] + 1;
			que.push(g);
		}
	}
	for (auto i : dist) {
		cout << i << " ";
	}
}

int counter[200005] = {};
void bfs2(Graph &G,int p,int x) {
	vector<int> dist(G.size() , -1);
	queue<int> que;
	
	dist[p] = 0;
	que.push(p);
	while (!que.empty()) {
		int v = que.front();
		que.pop();

		for (int g : G[v]) {
			if (dist[g] != -1)continue;
			dist[g] = dist[v] + 1;
			que.push(g);
			counter[g] += x;
		}
	}
}
long long int gcd(long long int a, long long int b) {
	long long int c = std::min(a, b);
	a = std::max(a, b);
	b = c;
	while (true) {
		c = a % b;
		a = b;
		b = c;
		if (c == 0)break;
	}
	return a;
}
long long int factorial(int start,int end = 1) {
	if (start == 0)return 1;
	return start == end ? end : start * factorial(start - 1,end);
}
long long int npr(int n, int r) {
	return factorial(n) / factorial(n - r);
}

long long int ncr(int n, int r) {
	return npr(n, r) / factorial(r);
}

int main()
{
	int n;
	std::unordered_map<std::string, int>dic;
	std::cin >> n;
	long long int rslt = 0;
	for (int i = 0; i < n; i++) {
		std::string a;
		std::cin >> a;
		sort(a.begin(), a.end());
		rslt += dic[a]++;
	}
	std::cout << rslt;
}

Measured memory_bytes: 10660
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1000000007;

void solve() {
  int a;
   cin >> a;
   cout << a + pow(a,2) + pow(a,3) << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 4196
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    ll n;
    cin >> n;
    ll ans = 0;
    rep(i, n) ans += i;
    cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;

int main(){
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL); 
	int x, a, b; cin >> x >> a >> b;
	cout << (x - a) % b << endl;
	return 0;
}




Measured memory_bytes: 3660
def solve(t):
    res_list = []
    for st in t:
        if st == "P":
            res_list.append("P")
        else:
            res_list.append("D")
    return "".join(res_list)


def main():
    t = input()
    res = solve(t)
    print(res)


def test():
    assert solve("PD?D??P") == "PDDDDDP"
    assert solve("P?P?") == "PDPD"


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 10692
#include <bits/stdc++.h>
using namespace std;
struct Point {
    double x, y;

    Point() = default;
    Point(double x, double y) : x(x), y(y) {}

    Point operator+(const Point &rhs) const {
        return Point(x + rhs.x, y + rhs.y);
    }

    Point operator-(const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }

    double operator*(const Point &rhs) const {
        return x * rhs.x + y * rhs.y;
    }

    double operator%(const Point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }

    bool operator<(const Point &rhs) const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
};
double dis(const Point& a, const Point& b) {
    return sqrt((a - b) * (a - b));
}

const int maxn = 1e5 + 5;
Point p[maxn];

double closest_pair(int l, int r) {
    if (l == r) return 1e9;
    if (r - l == 1) return dis(p[l], p[r]);
    int m = (l + r) >> 1;
    double d = min(closest_pair(l, m), closest_pair(m + 1, r));
    vector<int> vec;
    for (int i = m; i >= l && fabs(p[m].x - p[i].x) < d; --i) vec.push_back(i);
    for (int i = m + 1; i <= r && fabs(p[m].x - p[i].x) < d; ++i) vec.push_back(i);
    sort(vec.begin(), vec.end(), [&](int a, int b) { return p[a].y < p[b].y; });
    for (int i = 0; i < vec.size(); ++i) {
        for (int j = i + 1; j < vec.size() && fabs(p[vec[j]].y - p[vec[i]].y) < d; ++j) {
            d = min(d, dis(p[vec[i]], p[vec[j]]));
        }
    }
    return d;
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p, p + n);
    printf("%.20lf\n", closest_pair(0, n - 1));
}



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

void printTHS(int sec){
	int T = sec/3600;
	int H = sec/60%60;
	int S = sec%60;
	printf("%02d:%02d:%02d\n",T,H,S);
}

main(){
	while(true){
		// 時、分、秒
		int T ,H ,S;
		cin >>T>>H>>S;
		
		// T, H, S がすべて -1 のとき入力の終わりとします。
		if(T==-1){
			break;
		}
		
		int sec = 120*60 - (T*3600+H*60+S);
		
		printTHS(sec);
		
		printTHS(sec*3);
	}
}


Measured memory_bytes: 3144
#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++)

typedef long long ll;

ll mod = 998244353;

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    vector<vector<ll>> dp(c+1,vector<ll>(d+1,0));
    dp[a][b]=1;
    rept(i,a,c+1){
        rept(j,b,d+1){
            if(i==a&&j==b) continue;
        //    dp[i][j]=(dp[i-1][j]+dp[i][j-1]+(dp[i-1][j]-dp[i-1][j-1]*(i-1))*(j-1)+(dp[i][j-1]-dp[i-1][j-1]*(j-1))*(i-1)+dp[i-1][j-1]*(i-1)*(j-1))%mod;
            dp[i][j]=(dp[i-1][j]*j+dp[i][j-1]*i-(dp[i-1][j-1])*(i-1)*(j-1)+mod*(i-1)*(j-1))%mod;
        }
    }
    cout<<dp[c][d]<<endl;
    return 0;
}

Measured memory_bytes: 73616
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define MP make_pair
#define fi first
#define se second
#define PB push_back
#define CL clear
#define pii pair<int,int>
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = (int)(200010) + 10;
const int mod = 1e9+7;
const int inf = 1e9 + 10;
inline int rd() {
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+ch-'0'; ch=getchar();}
  return p*f;
}

int h,w; set<int>s; multiset<int> ans;
int sf[N];

signed main() {
  // freopen("a.in","r",stdin);
  h = rd(); w = rd();
  for(int i=1;i<=w;i++) s.insert(i),ans.insert(0),sf[i] = 0;
  for(int i=1;i<=h;i++) {
    int a = rd(); int b = rd();
    auto it = s.lower_bound(a); int shift = inf;
    while(it!=s.end() && (*it) <= b) {
      shift = min(shift , b - (*it) + 1 + sf[(*it)]);
      ans.erase(ans.find(sf[*it]));
      sf[*it] = -1; s.erase(it++);
    }

    if(b+1 <= w && shift != inf) {
      if(s.find(b+1) == s.end()) s.insert(b+1),ans.insert(shift),sf[b+1] = shift;
      else if(shift < sf[b+1]) ans.erase(ans.find(sf[b+1])),sf[b+1] = shift,ans.insert(shift);
    }

    if(ans.empty()) puts("-1");
    else printf("%lld\n",*(ans.begin()) + i);
  }
}

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

using namespace std;

const int N = 26;
const int DLIMIT = 3;

int D;
vector<int> C;
vector<vector<int>> S;
vector<int> last_day(N, -1);

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

// int calc_score(int d, int q) {
//   int res = 0;
//   for (int i = 0; i < N; i++) {

//   }
// }

int dfs(int d, vector<int> ld) {
  function<int(int, vector<int> &, int)> dfs = [&](int d, vector<int> &ld, int depth) {
    if (depth == DLIMIT || d == D) {
      return 0;
    }
    int res = 0, pos = 0;
    for (int i = 0; i < N; i++) {
      int t = ld[i];
      ld[i] = d;
      int cur = S[d][i];
      for (int j = 0; j < N; j++) {
        cur -= C[j] * (d - ld[j]);
      }
      if (chmax(res, cur + dfs(d + 1, ld, depth + 1))) {
        pos = i;
      }
      ld[i] = t;
    }
    return depth == 0 ? pos : res;
  };
  vector<int> _ld = ld;
  return dfs(d, ld, 0);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> D;
  C.resize(N), S.resize(D, vector<int>(N));
  for (int i = 0; i < N; i++) {
    cin >> C[i];
  }
  for (int i = 0; i < D; i++) {
    for (int j = 0; j < N; j++) {
      cin >> S[i][j];
    }
  }

  int score = 0;
  for (int d = 0; d < D; d++) {
    int pos = dfs(d, last_day);
    last_day[pos] = d;
    score += S[d][pos];
    for (int i = 0; i < N; i++) {
      score -= C[i] * (d - last_day[i]);
    }
    cout << pos + 1 << '\n';
  }
  return 0;
}


Measured memory_bytes: 3708
#include<iostream>

using namespace std;

int main(void)
{
    string S;
    cin >> S;
    if((S[2] == S[3]) && (S[4] == S[5]))
    {
        cout <<"Yes"<<endl;
    }
    else
    {
        cout <<"No"<<endl;
    }
    return 0;
}


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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,nb;
    string ch;
    cin>>n;
    cin>>ch;
    nb=1;
    for (int i=1;i<n;i++)
    {
        if (ch[i]!=ch[i-1])
        {
            nb++;
        }
    }
    cout<<nb;
    return 0;
}

Measured memory_bytes: 512
package main

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

func main() {
	var N, M int
	fmt.Scanln(&N, &M)
	sc := bufio.NewScanner(os.Stdin)
	broken := make(map[int]bool, M)
	for i := 0; i < M; i++ {
		sc.Scan()
		stair, _ := strconv.Atoi(sc.Text())
		broken[stair] = true
	}

	dp := make([]int, N+1)
	dp[0] = 1
	if broken[1] {
		dp[1] = 0
	} else {
		dp[1] = 1
	}

	for i := 2; i <= N; i++ {
		if broken[i] == false {
			dp[i] += dp[i-1] + dp[i-2]
		}
		dp[i] %= 1000000007
	}
	fmt.Println(dp[N])
}


Measured memory_bytes: 3840
import java.util.*;

class Main{
    static int count;
    static int n,s;
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);

	n = sc.nextInt();
	s = sc.nextInt();

	while(n!=0){
	    count = 0;

	    solve(0,0,0);

	    System.out.println(count);

	    n = sc.nextInt();
	    s = sc.nextInt();
	}
    }

    public static void solve(int pos, int sum, int num){
	//System.out.println(pos+" "+sum+" "+num);
	if(num>n){return;}
	if(num==n && sum==s){count++; return;}

	for(int i=pos; i<10; i++){
	    solve(i+1, sum+i, num+1);
	}
    }
}

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

int gcd(int a, int b) {
   int r;
   while((r = a % b) != 0)
   {
       a = b;
       b = r;
   }
   return b;
}

int main(void){
   int a, b, tmp;
   if (a < b){
       tmp = b;
b = a;
a = tmp;

   }
   while(cin >> a >> b) {
     int lcm = b/gcd(a,b)*a;
     cout << gcd(a,b) << " " << lcm << endl;
   }
   return 0;
}


Measured memory_bytes: 3068
#include "bits/stdc++.h"
#define MOD 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
#define pi acos(-1.0)
#define ri register int
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
#define int long long
const int maxn = 1e5 + 10;
inline int Max(int a, int b) { return a > b ? a : b; }
inline int Min(int a, int b) { return a > b ? b : a; }
namespace FastIO {
inline int read()
{
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (isdigit(c)) {
        r = 10 * r + c - '0';
        c = getchar();
    }
    return f * r;
}
inline void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) { write(x), puts(""); }
};
using namespace FastIO;
int tot, ver[maxn << 1], next[maxn << 1], head[maxn], N, K, depth[maxn], ans;
inline void add(int u, int v) { ver[++tot] = v, next[tot] = head[u], head[u] = tot; }
inline void dfs(int u, int fa)
{
    depth[u] = 1;
    for (ri i = head[u]; i; i = next[i]) {
        if (ver[i] == fa) {
            continue;
        }
        dfs(ver[i], u);
        if (depth[ver[i]] == K && u != 1) {
            ans++;
            continue;
        }
        depth[u] = Max(depth[ver[i]] + 1, depth[u]);
    }
}
signed main()
{
    //freopen("C:\Users\hjw\Downloads\testdata (4).in", "r", stdin);
    N = read(), K = read();
    for (ri i = 1; i <= N; ++i) {
        int dst = read();
        if (i == 1) {
            if (dst != 1)
                ++ans;
            continue;
        }
        add(i, dst), add(dst, i);
    }
    dfs(1, 0);
    writeln(ans);
    return 0;
}

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

#define LL long long

#define FOR(INDEX, START, END) for (int INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (int INDEX = 0; INDEX < (COUNT); ++INDEX)

struct Susi {
	LL type;
	LL point;
};
vector<Susi> susis;
LL countsOfType[100001] = {};

int main()
{
	int N, K;
	cin >> N >> K;
	susis.resize(N);
	REP(i, N) {
		cin >> susis[i].type >> susis[i].point;
	}

	sort(susis.begin(), susis.end(), [](Susi const& a, Susi const& b) {
		return a.point > b.point;
	});

	LL totalPoint = 0;
	LL typeCount = 0;
	REP(i, K) {
		if (countsOfType[susis[i].type] == 0) {
			typeCount++;
		}

		countsOfType[susis[i].type]++;
		totalPoint += susis[i].point;
	}

	LL maxScore = totalPoint + typeCount * typeCount;

	LL eatIndex = K - 1;
	LL otherIndex = K;
	while (eatIndex >= 0) {
		if (countsOfType[susis[eatIndex].type] > 1) {
			LL newEat = -1;
			while (otherIndex < N) {
				if (countsOfType[susis[otherIndex].type] == 0) {
					newEat = otherIndex;
					break;
				}
				++otherIndex;
			}

			if (newEat < 0) {
				break;
			}

			// たべかえる
			totalPoint -= susis[eatIndex].point;
			totalPoint += susis[newEat].point;
			countsOfType[susis[eatIndex].type]--;
			countsOfType[susis[newEat].type]++;
			typeCount++;

			otherIndex = newEat + 1;

			LL score = totalPoint + typeCount * typeCount;
			if (score > maxScore) {
				maxScore = score;
			}

			--eatIndex;
		}
		else {
			--eatIndex;
		}
	}

	cout << maxScore << endl;

	return 0;
}


Measured memory_bytes: 2560
import java.util.*;

public class Main{
  public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		String str = null;
		for(int i = A;i <= B;i++) {
			if(i % K == 0) {
				str = "OK";
			}
		}
		if(str != null) {
			System.out.println("OK");
		}else {
			System.out.println("NG");
		}
	}
}

Measured memory_bytes: 35852
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  ll N,M;
  cin>>N>>M;
  
  vector<ll>a(M);
  vector<bool>stair(N+1);
  vector<ll>dp(N+1);
  dp[0]=1;
  
  rep(i,N+1){
    stair[i]=true;
  }

  
  rep(i,M){
    cin>>a[i];
    stair[a[i]]=false;
  }
  
  
 for(ll i=1;i<N+1;i++){
   if(stair[i]){
   if(i>=2&&stair[i-2]==true){
dp[i]+=dp[i-2];
     dp[i]%=mod;
   }
   if(stair[i-1]){
     dp[i]+=dp[i-1];
     dp[i]%=mod;
   }
   }
 }
  
  cout<<dp[N]<<endl;
}
  

    

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;
const int mod = 1e9 + 7;

int main()
{
    long long n, k;
    long long ans = 0;
    cin >> n >> k;
    vector<bool> t(n, false);

    for (int i = 0; i < k; i++)
    {
        long long d;
        cin >> d;
        for (int j = 0; j < d; j++)
        {
            long long a;
            cin >> a;
            t.at(a - 1) = true;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (!t.at(i))
        {
            ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

long long calc(int n){
    int res = 0;
    
    while (n > 0){
        res += n % 10;
        n /= 10;
    }
    return res;
}

int main(void){
   long long n;
   cin >> n;
   long long res = 1LL<<60;
   
   for (long long i = 1; i < n; i++){
       long long j = n - i;
       long long temp = calc(i) + calc(j);
       res = min(res,temp);
   }
   cout << res << endl;
}


Measured memory_bytes: 3596
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
int a,b,c,d;
ll dp[1005][1005];
ll comb[1005][1005];

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;
		y=0;
	}
	return d;
}

ll mod_inverse(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (m+x%m)%m;
}

int main(void){
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	for(int i=0;i<=n;i++){
		comb[i][i]=1;
		comb[i][0]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%MOD;
		}
	}
	dp[0][0]=1;
	for(int i=0;i<n;i++){
		for(int k=0;k<=n;k++){
			dp[i+1][k]+=dp[i][k];
			dp[i+1][k]%=MOD;
			ll cal=1;
			ll v=0;
			for(int j=(i+1);j<=n-k;j+=(i+1)){
				cal=cal*comb[n-k-v*(i+1)][i+1]%MOD;
				//printf("%lld %lld %d\n",cal,n-k-v*(i+1),i+1);
				cal=cal*mod_inverse(v+1,MOD)%MOD;
				//printf("%lld %lld %d\n",cal,n-k-v*(i+1),i+1);
				v++;
				if(i+1<a || i+1>b)continue;
				if(v<c || v>d)continue;
				if(j+k<=n){
					dp[i+1][j+k]+=dp[i][k]*cal%MOD;
					dp[i+1][j+k]%=MOD;
					if(dp[i+1][j+k]>0){
						//printf("dp %d %d %lld\n",i+1,j+k,dp[i+1][j+k]);
					}
				}
			}
		}
	}
	printf("%lld\n",dp[n][n]);
	return 0;
}


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


int main()
{
	int N;
	scanf("%d", &N);
	std::vector<std::pair<long double, long double>> xy(N);
	for (auto& e: xy) scanf("%Lf%Lf", &e.first, &e.second);
	long double sum{};
	for (int i{}; i < N; i++)
		for (int j{}; j < N; j++)
			sum += std::hypot(xy[i].first - xy[j].first, xy[i].second - xy[j].second);
	printf("%.10Lf\n", sum / N);

	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int BIG = 2e9 + 55;
const int maxN = 1e5 + 55;

char s[maxN], t[maxN];
int psums[maxN], psumt[maxN];

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

    cin >> (s + 1);
    cin >> (t + 1);

    int n = strlen(s + 1);
    int m = strlen(t + 1);

    for(int i = 1; i <= n; i++){
        //cerr << ((s[i] == 'B') ? 1 : 2) << ' ';
        psums[i] = psums[i - 1] + ((s[i] == 'B') ? 1 : 2);
    }
    //cerr << '\n';

    for(int i = 1; i <= m; i++){
        //cerr << ((t[i] == 'B') ? 1 : 2) << ' ';
        psumt[i] = psumt[i - 1] + ((t[i] == 'B') ? 1 : 2);
    }
    //cerr << '\n';

    int q;  cin >> q;
    while(q--){
        int a, b, x, y; cin >> a >> b >> x >> y;
        int s1 = psums[b] - psums[a - 1];
        int s2 = psumt[y] - psumt[x - 1];
        //cerr << s1 << ' ' << s2 << '\n';
        if((s1 - s2) % 3 == 0){
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int isp(int n){
    if(n==2){
        return 1;
    }
    else if(n==3){
        return 1;
    }
    else if(n==5){
        return 1;
    }
    else if(n%2==0){
        return 0;
    }
    else if(n%3==0){
        return 0;
    }
    else if(n%5==0){
        return 0;
    }
    int i=3,sq=(int)sqrt(n);
    while(i<=sq){
        if(!(n%i)){
            return 0;
        }
        i+=2;
    }
    return 1;
}


int main(){
    int n,a,count=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        count+=isp(a);
        if(isp(a)){
        }
    }
    cout << count <<endl;
}

Measured memory_bytes: 3104
#include <iostream>

bool fit(int m, int n, int* w, int width)
{
	int tray = 0;
	int sum_of_w = 0;
	int books;
	for (books=0; books<n; books++) {
		while (sum_of_w + w[books] > width && tray<m) { tray++; sum_of_w = 0; }
		if (tray == m) return false;
		sum_of_w += w[books];
	}
	return true;
}

int getWidth(int m, int n, int* w)
{
	int lb = w[0], ub = 1500000;
	while (lb < ub) {
		if (lb+1==ub) break;
		int mid = (lb + ub) / 2;
		if (fit(m, n, w, mid)) ub = mid;
		else lb = mid;
	}
	if (fit(m, n, w, lb)) return lb;
	else return ub;
}

int main()
{
	int m, n;
	while (true) {
		std::cin >> m >> n;
		if (m == 0) break;
		int* w = new int[n];
		for (int i=0; i<n; i++) std::cin >> w[i];
		std::cout << getWidth(m, n, w) << std::endl;
		delete[] w;
	}
	return 0;
}



Measured memory_bytes: 3012
#include<stdio.h>

int main()
{

    int a, b, cnt = 0,i, N;

    scanf("%d", &N);
    for(i = 0; i < N; i++)
    {
        scanf("%d %d", &a, &b);
        cnt += b -a + 1;
    }
    printf("%d", cnt);

}




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

typedef long long LL;

const int N = 1e5 + 10;

int n, m, v, p, a[N];

bool ok(int x){
	LL cur = 0LL + a[x] + m;

	if(cur < a[p - 1])	return 0;

	int lft = v;
	for(int i=0; i<n; i++){
		if(a[i] <= a[x])	lft--;
	}

	lft = lft - (p - 1);

	if(lft <= 0)	return 1;

	LL sum = 0;
	for(int i=p-1; i<x; i++){
		if(a[i] > a[x])	sum = sum + cur - a[i];
	}

	return sum >= 1LL * lft * m;
}

int main(){
	scanf("%d %d %d %d", &n, &m, &v, &p);
	for(int i=0; i<n; i++)	scanf("%d", a+i);
	sort(a, a+n, greater<int>());

	int low = p, top = n - 1, ans = p, mid;

	while(low <= top){
		mid = low + top >> 1;
		if(ok(mid)){
			ans = max(ans, mid + 1);
			low = mid + 1;
		} else {
			top = mid - 1;
		}
	}

	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 640