akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;   
#define ll long long
#define ull unsigned long long
// #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> 
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define inf 9e18
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// Comment this out for interactice problem
// #define endl '\n'
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output

int main() 
{ 
    fastio;
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);    

    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll r=0;
    ll w=0;
    for (int i = 0; i < n; ++i)
    {
        if(s[i]=='W'){
            w++;
        }
        else{
            r++;
        }
    }
    ll ans=min(r, w);

    ll x=0;
    for (int i = n-1; i>=n-w; i--)
    {
        if(s[i]=='R'){
            x++;
        }
    }
    ans=min(ans, x);
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3776
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
#include<string.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007



ll dp[101][100001] = {};
int a[101];
ll sum[100001];
int n,k;

ll rec(int idx , int left){
	if(idx<1 && left!=0) return 0;
	if(idx<1 && left==0) return 1;
	ll& ans = dp[idx][left];
	if(ans!=-1) return ans%mod;
	
	ans=0;
	for(int i=0;i<=a[idx] ; ++i){
		if(left-i>=0) ans += rec(idx-1 , left-i);
		ans%=mod;
	}
	return ans%mod; 
}

int main(){
	//memset(dp,1,sizeof(dp));
	IOS;
	cin >> n >> k;
	for(int i=1;i<=n ;++i){
		cin >> a[i];
	}

	for(int i=0;i<=a[1] ; ++i){
		dp[1][i] = 1;
	}
	
	for(int i=2; i <=n ; ++i){
		sum[0] = dp[i-1][0];
		for(int c=1;c<=k ; ++c){
			sum[c] = (sum[c-1] + dp[i-1][c] + mod) % mod;
		}
		for(int j = 0;j<=k ; ++j){
			if(j-min(j,a[i])-1<0)dp[i][j] = sum[j];
			else dp[i][j] = sum[j] - sum[j-min(j,a[i])-1];
		}
	}
	cout << (dp[n][k] + mod)%mod << endl;
}

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

c = [list(map(int, input().split())) for i in range(3)]


a1 = 0
b1, b2, b3 = c[0][0], c[0][1], c[0][2]
a2 = c[1][0]-b1
a3 = c[2][0]-b1

check = []
check.append(c[1][1] == a2+b2)
check.append(c[2][1] == a3+b2)
check.append(c[1][2] == a2+b3)
check.append(c[2][2] == a3+b3)

if sum(check) == 4:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 8952
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define yes "Yes\n"
#define no "No\n"
//int m,n;
int i,j,k,l;
int a,b,c,d,e,f,g;
//int sum,total;
//long long int ;
//float ;
//double ;
//char a[101],b[101],s[101],t[101],u[101];
char s1[10],s2[10];
int main(void){
    scanf("%d %d",&a,&b);
    for (i = 0; i < a; i++)
    {
        c=(c*10)+b;
    }
    for (i = 0; i < b; i++)
    {
        d=(d*10)+a;
    }
    
    if ( c/(int)(pow(10,a-1)) > d/(int)(pow(10,b-1)) )
    {
        printf("%d\n",d);
    } else if ( c/(int)(pow(10,a-1)) == d/(int)(pow(10,b-1)) )
    {
        if (c>d)
        {
            printf("%d\n",d);
        } else
        {
            printf("%d\n",c);
        }
    } else
    {
        printf("%d\n",c);
    }
    
    
    
    
    return 0;
}

Measured memory_bytes: 128
import Data.Array.MArray
import Data.Array.IO
import Data.List.Split
import Data.Int

type Int32Array = IOUArray Int32 Int32
main = do
  num <- fmap (\str -> (read str :: Int32)) getLine
  strLs <- fmap (splitOn " ") getLine
  let xs = fmap (\str -> (read str :: Int32)) strLs
  arr <- (newListArray ((0 :: Int32), num - 1) xs :: IO Int32Array)
  arr' <- getElems arr
  prettyPut arr'
  loop1 1 num arr

loop1 :: Int32 -> Int32 -> Int32Array -> IO ()
loop1 cur to arr
  | cur < to = do
    key <- readArray arr cur
    loop2 (cur-1) arr key
    arr' <- getElems arr
    prettyPut arr'
    loop1 (cur + 1) to arr
  | cur == to = return ()

loop2 :: Int32 -> Int32Array -> Int32 -> IO ()
loop2 cur arr key = do
  if (cur >= 0) then do
    value <- readArray arr cur
    if (value > key) then do
      writeArray arr (cur+1) value
      loop2 (cur-1) arr key
    else
      writeArray arr (cur+1) key
  else
    writeArray arr (cur+1) key

prettyPut xs = do
  let strXs = fmap show xs
  putStrLn $ foldl1 (\x y -> x ++ " " ++ y) strXs


Measured memory_bytes: 5040
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a
lcd = 1

N = int(input())
ts = [int(input()) for i in range(N)]

for t in ts:
    lcd = (lcd*t)//gcd(lcd,t)

print(lcd)

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

typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxn 101
#define int ll


int A[maxn],N;

int32_t main(){
	fast;
	
	cin>>N;
	
	FOR(i,1,N) cin>>A[i];
	
	int ans = 0;
	FOR(i,1,N) FOR(j,i+1,N) FOR(k,j+1,N){
		int a = A[i]; int b = A[j]; int c = A[k];
		if (a == b || a == c || b == c) continue;
		if (a + b > c && a + c > b && b + c > a) ans++;
	}
	cout<<ans;
}


Measured memory_bytes: 3652
import itertools

L,R = map(int,input().split())
if R - L + 1 >= 2019:
    ans = 0
else:
    LL = L % 2019
    RR = R % 2019
    if LL < RR:
        Amari_List = list(range(LL,RR+1))
        ans = 2019
        for v1,v2 in itertools.combinations(Amari_List, 2):
            ca = (v1*v2) % 2019 
            if  ca < ans:
                ans = ca
    else:
        ans = 0

print(ans)





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

int main() {
  string o, e;
  cin >> o >> e;
  
  int l = o.size() + e.size();
  vector<char> ans(0);
  for(int i = 0; i < l; i++){
    if(i % 2) cout << e.at(i / 2);
    else cout << o.at(i / 2);
  }
}

Measured memory_bytes: 256
# coding: utf-8
S = input()[:-1]
n = len(S)
for _ in range(n):
    flg = 1
    if n % 2 == 1:
        S = S[:-1]
        n -= 1
        continue
    for i in range(n // 2):
        if S[i] != S[n // 2 + i]:
            flg = 0
    if flg:
        print(n)
        break
    S = S[:-2]
    n -= 2


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;


int main(void)
{
    int N, Y;
    cin >> N >> Y;
    
    Y /= 1000;

    int x = 0;
    int y = 0;
    int z = 0;
    int val = 0;
    bool found = false;
    for(x = 0; x <= N; x++){
        for(y = 0; y <= N; y++){
            z = N - x - y;
            if(z < 0) continue;
            val = 10 * x + 5*y + z;
            
            if(val == Y) {
                found = true;
                break;
            }
        }
        if(val == Y) break;
    }

    if(found){
        cout << x << " " << y << " " << z << endl;
    } else {
        cout << "-1 -1 -1" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3624
package main

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

func main() {
	fmt.Println(ModFactorial(ReadInt()))
}

const Mod = int(1e9) + 7

func ModAdd(a, b int) int  { return ((Mod + a%Mod) + (Mod + b%Mod)) % Mod }
func ModMul(a, b int) int  { return (Mod + a%Mod) * (Mod + b%Mod) % Mod }
func ModInverse(n int) int { return ModPow(n, Mod-2) }
func ModDiv(a, b int) int  { return a * ModInverse(b) }
func ModPow(a, b int) int {
	x := 1
	for b > 0 {
		if b&1 == 1 {
			x = x * a % Mod
		}
		a = a * a % Mod
		b >>= 1
	}
	return x
}
func ModFactorial(n int) int      { return fac[n] }
func ModPermutation(n, r int) int { return fac[n] * finv[n-r] % Mod }
func ModCombination(n, k int) int { return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod }

var fac, finv, inv []int

func init() {
	const MAX = 5 * 1e5
	fac, finv, inv = make([]int, MAX+1), make([]int, MAX+1), make([]int, MAX+1)
	fac[0], fac[1], finv[0], finv[1], inv[1] = 1, 1, 1, 1, 1
	for 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
	}
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


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

int main() {
    string s;
    cin >> s;
    int n=s.size();
    int ans=0;
    for(int i=0; i<n; i++){
        int j=i-1;
        while(j+1<n & (s[j+1] == 'A' | s[j+1] == 'T' | s[j+1] == 'C' | s[j+1] == 'G')) j++;
        ans = max(ans, j-i+1);
        // cout << i << " " << ans << endl;
    }
    cout << ans << endl;
}

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

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

int main(){
	long long int n, k;
	cin >> n >> k;
	n %= k;

	if(abs(n - k) < n) n = abs(n - k);

	cout << n;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    typedef unsigned long long ull;
    typedef long long ll;
    typedef long double ld;
    #define FOR(type,a,b,c,d) for(type i = a;i b c;i += d)
    #define QUICK ios_base::sync_with_stdio(0);cout << fixed;
    #define MOD 1000000007

    string upper(string);
    string lower(string);
    bool isalup(string);
    bool isalow(string);

    int main(){

        int a,ans = 0;;
        cin >> a;
        string b;
        cin >> b;
        int i = 0;
        int j = a-1;
        while(i<j){
            if(b[i]=='R')
                i++;
            else if(b[j]=='W')
                j--;
            else
                ans++,i++,j--;
        }
        cout << ans;

        return 0;
    }









                string upper(string a){
                    for(char& c:a){
                        if(islower(c))
                            c -= 32;
                       }
                    return a;
                }
                    string lower(string a){
                        for(char& c : a){
                            if(isupper(c))
                                c += 32;
                        }
                        return a;
                    }
                    bool isalup(string a){
                        for(char& c: a){
                            if(islower(c))
                                return false;
                        }
                        return true;
                    }
                    bool isalow(string a){
                        for(char& c:a){
                            if(isupper(c))
                                return false;
                        }
                       return true;
                    }


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

using namespace std;

int main()
{
	vector<int> a(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(a.begin(), a.end());
	cout << a[2] - a[0] << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
template <class T> void corner(bool flg, T hoge) {
    if(flg) {
        cout << hoge << endl;
        exit(0);
    }
}
#define all(v) v.begin(), v.end()
#define inputv(v, n)                                                           \
    vl v;                                                                      \
    rep(i, n) {                                                                \
        ll x;                                                                  \
        cin >> x;                                                              \
        v.push_back(x);                                                        \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
struct edge {
    ll to, cost;
};
vector<edge> G[MAX_N];
vl visited;
vl Euler_tour,Euler_tour_cost;

void add(ll a, ll b, ll c = 1) { G[a].push_back((edge) { b, c }); }

void resetv(void) { visited = vl(n, 0); }

vl par(MAX_N, -1), toposo, ko(MAX_N, 0), cost(MAX_N, 0),L(MAX_N,-1),R(MAX_N,0);

void dfs_tree(ll x, ll a){
    visited[x] = 1;
    for (edge i : G[x]) {
        if (visited[i.to] == 0) {
            Euler_tour.push_back(i.to);
            Euler_tour_cost.push_back(i.cost);
            dfs_tree(i.to, a + i.cost);
            Euler_tour_cost.push_back(-i.cost);
            Euler_tour.push_back(x);
            par[i.to] = x;
        }
    }
}

void root(ll x) {
    Euler_tour.push_back(x);
    dfs_tree(x, 0);
}

struct segtree {
    ll N;
    vl dat;
    void init(ll n) {
        N = 1;
        while (N < n) N *= 2;
        dat = vl(N * 2 + 1);
        for (ll i = 0; i < 2 * N - 1; i++)
            dat[i] = 0;
    }
    // update k th element
    void add(ll k, ll a) {
        k += N - 1; // leaf
        dat[k] += a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];
        }
    }
    // sum of [a, b)
    ll query(ll a, ll b) { return query(a, b, 0, 0, N); }
    ll query(ll a, ll b, ll k, ll l, ll r) {
        if (r <= a or b <= l) return 0;
        if (a <= l and r <= b) return dat[k];
        ll m = (l + r) / 2;
        return (query(a, b, k * 2 + 1, l, m) + query(a, b, k * 2 + 2, m, r));
    }
};

int main() {
    cin >> n;
    rep(i, n) {
        cin >> x;
        rep(j, x) {
            cin >> a;
            add(a, i, 0);
            add(i, a, 0);
        }
    }

    resetv();
    root(0);

   rep(i,Euler_tour.size()) {
       a = Euler_tour[i];
       if (L[a] == -1)L[a] = i;
       R[a] = i;
    }

   segtree SEG;
   SEG.init(n * 2);

   rep(i, Euler_tour_cost.size()) {
       SEG.add(i, Euler_tour_cost[i]);
   }

   cin >> q;
   rep(i, q) {
       cin >> a;
       if (a == 0) {
           cin >> x >> y;
           SEG.add(L[x] - 1, y);
           SEG.add(R[x], -y);
       }
       else {
           cin >> x;
           cout << SEG.query(0, R[x])<<endl;
       }
   }
}


Measured memory_bytes: 56876
#include <iostream>
#include <vector>

int main() {
  unsigned int N, K;
  std::cin >> N >> K;
  const unsigned long mod = 1000000007;

  unsigned long sum = 0;
  for (unsigned long i = K; i <= N + 1; ++i) {
    // 0, 1, ..., i - 1
    const unsigned long min_sum = (i - 1) * i / 2;
    // N - i + 1, N - i + 2, ..., N
    const unsigned long max_sum = (2 * N - i + 1) * i / 2;
    const unsigned long num = (max_sum - min_sum + 1) % mod;
    sum = (sum + num) % mod;
  }

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


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

using namespace std;
int x,a;
int main()
{
    //freopen("A.inp","r",stdin);
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> x >> a;
    if (x<a) cout << 0;
    else cout << 10;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {

	var N int
	var min, ans = math.MaxInt32, 0
	fmt.Scan(&N)
	for i := 0; i < N; i++ {
		var tmp int
		fmt.Scan(&tmp)
		if min > tmp {
			ans++
			min = tmp
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5504
import sys

N = int(input())
b = list(map(int, input().split()))

a = [0] * N
a[0] = b[0]
for i in range(len(b) - 1):
    if b[i] > b[i + 1]:
        a[i + 1] = b[i + 1]
    else:
        a[i + 1] = b[i]
a[-1] = b[-1]

print(sum(a))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, dp[1007][1007];
string s[1007];
const int mod = 1e9 + 7;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> s[i];
	}
	dp[0][0] = 1;
	for(int i = 1; i < n; i++){
		if(s[i][0] == '#') break;
		dp[i][0] = 1;
	}
	for(int i = 1; i < m; i++){
		if(s[0][i] == '#') break;
		dp[0][i] = 1;
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			if(s[i][j] == '#') continue;
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
	cout << dp[n - 1][m - 1];
}


Measured memory_bytes: 5248
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
R = [0 for j in range(N)]
for i in range(N-1):
  for j in range(N):
    if j <= i:
      continue
    xd = abs(i - X)
    yd = abs(j - Y)
    dist = min(
      j - i,
      xd + yd + 1
    )
    R[dist] += 1
for r in R[1:]:
  print(r)

Measured memory_bytes: 47580
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leading zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    ll a[n+2];
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    ll x=a[0];
    ll y=a[n-1];
    ll mn=LLONG_MAX;
    for(ll i=x;i<=y;i++){
        ll sum=0;
        for(int j=0;j<n;j++){
            sum+=(i-a[j])*(i-a[j]);
        }
        mn=min(mn,sum);
    }
    cout<<mn<<endl;
}


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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int N; cin >> N;
    
    int L[N]; rep(i, N) cin >> L[i];
    //int L[N]; rep(i, N) L[i] = 1000;
    int ruiseki[2001] = {};
    ll ans = 0;
    rep(i, N) ruiseki[L[i]]++;
    for(int i = 1; i < 2001; i++) ruiseki[i] += ruiseki[i-1];
    for(int i = 0; i < N; i++){
        for(int j = i+1; j < N; j++){
            int a = L[i], b = L[j];
            //abs(a-b)より大でa+bより小なものはいくつか
            //ruiseki[a+b-1] - ruiseki[abs(a-b)]
            //さらに, a, bがこの範囲に入ってたらminus2
            ans += ruiseki[a+b-1] - ruiseki[abs(a-b)];
            if(abs(a-b) < a) ans--;
            if(abs(a-b) < b) ans--;

        }
    }
    //rep(i, 20) cout << ruiseki[i] << " "; cout << endl;
    cout << ans/3 << endl;
    return 0;
}

void solve(){}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
      Scanner sc = new Scanner(System.in);    //整数の入力
      int D = sc.nextInt();
      int N = sc.nextInt();
      if(N==100){
        System.out.print((int) (Math.pow(100, D) * 101)) ;
      } else {
        System.out.print((int) (Math.pow(100, D) * N));
      }
  }
}

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

int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; i++) {
        cin >> L[i];
    }
    sort(L.rbegin(), L.rend());
    int count = 0;
    for(int a = 0; a < N-2; a++) {
        for(int b = a+1; b < N-1; b++) {
            for(int c = b+1; c < N; c++) {
                if(L[a] +L[b] <= L[c]) {
                    continue;
                }
                if(L[a] + L[c] <= L[c]) {
                    break;
                }
                if(L[b] + L[c] <= L[a]) {
                    break;
                }
                //cout << L[a] << " "<< L[b] << " " << L[c] << endl;
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
X,Y,A,B,C= map(int, input().split())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
R = list(map(int,input().split()))

P = sorted(P,reverse = True)
Q = sorted(Q,reverse = True)
R = sorted(R,reverse = True)

ans = 0
l = []

for i in range(X):
    l.append(P[i])
for j in range(Y):
    l.append(Q[j])
    
l = sorted(l)


for k in range(C):
    if R[k] > l[k]:
        l[k] = R[k]
    else:
        break

print(sum(l))

Measured memory_bytes: 23328
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int L = Integer.parseInt(sc.next());
        int R = Integer.parseInt(sc.next());

        sc.close();

        if (R - L >= 2019) {

            System.out.println(0);
            System.exit(0);
        }

        long mod2019;
        long min = 2019;

        for (long i = L; i < R; i++) {

            for (long j = i+1; j <= R; j++) {

                mod2019 = (i*j)%2019;

                if (min > mod2019) {

                    min = mod2019;
                }

//                if (min == 0) {
//
//                    break;
//                }
            }

//            if (min == 0) {
//
//                break;
//            }
        }

        System.out.println(min);
    }

}


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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    int a, b, c;
    cin >> a >> b >> c;
    vector<int> v = {a, b, c};
    sort(v.begin(), v.end());
    if ( (v[0] == v[1] || v[1] == v[2]) && v[0]!=v[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;


    if (argc == 2 && atoi(argv[1]) == 123456789) cout << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

char in[200001];

int ll[30];
char ans[200001];
int len[200001];
int next[200001];
int all = (1<<27) - 1;

int main(){
        scanf("%s", in);
        int n = strlen(in);
        for(int i=0; i<26; i++) ll[i] = -1;
        next[n] = -1;
        len[n] = 1;
        ans[n] = 'a';
        for(int i=n-1; i>=0; i--){
                ll[in[i]-'a'] = i;
                len[i] = n+10;
                for(int j=25; j>=0; j--){
                        if(ll[j] == -1){
                                len[i] = 1;
                                ans[i] = j + 'a';
                                next[i] = -1;
                        }
                        else if(len[i] >= len[ll[j]+1] + 1){
                                len[i] = len[ll[j]+1] + 1;
                                ans[i] = j + 'a';
                                next[i] = ll[j] + 1;
                        }
                }
        }

//      for(int i=0; i<n; i++) printf("%d ", next[i]); printf("\n");
//      for(int i=0; i<n; i++) printf("%d ", len[i]); printf("\n");
//      for(int i=0; i<n; i++) printf("%d ", ans[i]); printf("\n");
        for(int t=0; t!=-1; t = next[t]) printf("%c", ans[t]);
        return 0;
}

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

using namespace std;

using ll = long long;

mt19937 mt(736);


void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
	int h, w;

	cin >> h >> w;

	vector<string> field(h);

	for (auto &row : field)
		cin >> row;

	vector<vector<int>> dp(h, vector<int>(w, numeric_limits<int>::max()));
	dp[0][0] = field[0][0] == '#' ? 1 : 0;

	for (int y = 0; y < dp.size(); y++)
		for (int x = 0; x < dp[y].size(); x++)
		{
			if (y + 1 < dp.size())
				dp[y + 1][x] = min(dp[y + 1][x], dp[y][x] + (field[y + 1][x] == field[y][x] ? 0 : 1));
			if (x + 1 < dp[y].size())
				dp[y][x + 1] = min(dp[y][x + 1], dp[y][x] + (field[y][x + 1] == field[y][x] ? 0 : 1));
		}

	cout << (dp.back().back() + 1) / 2 << endl;
}


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

	cout << fixed;

#ifdef LOCAL
	auto st = clock();

	ifstream fin("../input.txt");

	solve(fin);

	cout << "clock: " << (clock() - st) / (double) CLOCKS_PER_SEC << endl;
#else
	solve();
#endif

	return 0;
}


Measured memory_bytes: 384
from collections import deque
A = deque(list(input()))
B = deque(list(input()))
C = deque(list(input()))
card = "a"
while True:
  if card == "a":
    if len(A) == 0:
      print("A")
      break
    card = A.popleft()
  elif card == "b":
    if len(B) == 0:
      print("B")
      break
    card = B.popleft()
  else:
    if len(C) == 0:
      print("C")
      break
    card = C.popleft()

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

int main() {
  int N;
  cin >> N;
  int A[21]{};
  int B[51]{};
  int C[51]{};
  for (int i = 0; i < N; ++i) cin >> A[i];
  for (int i = 0; i < N; ++i) cin >> B[i];
  for (int i = 0; i < N - 1; ++i) cin >> C[i];
  
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    ans += B[A[i] - 1];
    if (i > 0 && (A[i] == (A[i-1]+1))) {
      ans += C[A[i-1]-1];
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
N, W = map(int, input().split())
#i個目の品物までで重さw以下のときの価値の最大値 
dp = [[0]*(W+1) for _ in range(N+1)]
"""
dp[i, wi:W+1] = max(i番目の重さwiの品物を入れた場合, 入れなかった場合)
         = np.max(dp[i-1, :W-wi+1] + v, dp[i-1, wi:W+1])
"""

for i in range(1, N+1):
    w, v = map(int, input().split())

    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])


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

int main()
{
	int n,m;
	while(cin >> n >> m){
		if(!n && !m)
			break;
		bool card[100001] = {false};
		for(int i=0;i<m;i++){
			int a;
			cin >> a;
			card[a] = true;
		}

		int ma = 1;
		for(int i=1;i<=n;i++){
			int sum = 0;
			bool flag = card[0];
			int j = i;
			while(j <= n){
				if(card[j] == true || flag){
					sum++;
					if(card[j] == false && flag == true)
						flag = false;
					j++;
				}
				else
					break;
			}
			ma = max(ma,sum);
		}
		cout << ma << endl;
	}
	return 0;
}

Measured memory_bytes: 0
n = int(input())
works = [[int(x) for x in input().split()] for _ in range(n)]
for i in range(n): works[i][0], works[i][1] = works[i][1], works[i][0]
works.sort()
time = 0
judge = True
for i in range(n):
  time += works[i][1]
  if time > works[i][0]:
    judge = False
    break
if judge: print("Yes")
else: print("No")

Measured memory_bytes: 38748
#include<bits/stdc++.h>
#define ll long long int
#define __ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1)
using namespace std;

int a[11111], b[11111],c[111111];

int main()
{
__

int n,ans=0;

cin >> n;

for(int i=1;i<=n;i++) cin >> a[i];

for(int i=1;i<=n;i++) cin >>b[i];

for(int i=1;i<=n-1;i++) cin >> c[i];

for(int i=1;i<=n;i++)
{
ans+=b[a[i]];

if(a[i]-a[i-1] == 1) ans+=c[a[i-1]];

}

cout << ans << '\n';

return 0;
}

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

typedef long long LL;

int main(){
    LL a=2,b=1,c,n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        c=a+b;
        a=b;b=c;
    }
    printf("%lld\n",a);
    return 0;
}


Measured memory_bytes: 128
//inlclude before define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<deque>
#include<iomanip>
#include<set>
#include<unordered_set>
#include<tuple>
#include<map>
#include<memory>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<double> VD;
typedef pair<int, int> P1;
typedef long long int ll;

//number
#define INF 1e9
#define NUM 1000000007

//itr
#define all(x) begin(x),end(x)

//repeat
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);i++)
#define RREPS(i,x) for(int i=((int)(x));i>=0;i--)

//max,min
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))

//function

/*ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}*/

/*ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a * (b / g);
}*/

/*int dig(int a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}*/

//grid template
int x[] = { -1, 0, 1, 0 };
int y[] = { 0,-1,0,1 };
int xx[] = { -1,-1,1,1 };
int yy[] = { 1,-1,1,-1 };

int main() {
	int a, b, c;
	cin >> a >> b >> c;

	if (b / a >= c) {
		cout << c << endl;
	} else {
		cout << b/a << endl;
	}

}




 

Measured memory_bytes: 256
n = gets.to_i
a = gets.split.map(&:to_i)

sum = a.reduce(&:+)
snuke_sum = a[0]
min_diff = (sum - 2 * snuke_sum).abs
1.upto(n-2) do |i|
  snuke_sum += a[i]
  min_diff = [min_diff, (sum - 2 * snuke_sum).abs].min
end

puts min_diff

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

namespace AtCoder
{
	class Program
	{
		public static void Main()
		{
			var count = IO.ReadInt();
			IO.Write(Enumerable.Range(0 , count).Select(iIndex =>
			{
				return IO.Read();
			})
			.Distinct()
			.Count());
		}
	}

	public static class IO
	{
		public static string   Read()								 { return Console.ReadLine(); }
		public static string[] ReadArray(char iSplitter = ' ')		 { return Read().Split(iSplitter); }
		public static int	   ReadInt()							 { return int.Parse(Read()); }
		public static int[]	   ReadIntArray(char iSplitter = ' ')	 { return ReadArray().Select(iText => int.Parse(iText)).ToArray(); }
		public static long	   ReadLong()							 { return int.Parse(Read()); }
		public static long[]   ReadLongArray(char iSplitter = ' ')	 { return ReadArray().Select(iText => long.Parse(iText)).ToArray(); }
		public static double   ReadDouble()							 { return double.Parse(Read()); }
		public static double[] ReadDoubleArray(char iSplitter = ' ') { return ReadArray().Select(iText => double.Parse(iText)).ToArray(); }
		public static char[]   ReadCharArray()						 { return Read().ToCharArray(); }

		public static void Write(string iValue)									   { Console.WriteLine(iValue); }
		public static void Write(int iValue)									   { Console.WriteLine(iValue); }
		public static void Write(IEnumerable<int> iValue , string iJoinWord = " ") { Console.WriteLine(string.Join(iJoinWord , iValue)); }
		public static void Write(long iValue)									   { Console.WriteLine(iValue); }
		public static void Write(double iValue)									   { Console.WriteLine(iValue); }
		public static void Write(decimal iValue)								   { Console.WriteLine(iValue); }
		public static void Write(bool iValue)									   { Console.WriteLine(iValue ? "Yes" : "No"); }
	}

	public static class Util
	{
		public static long Gcd(long i0 , long i1) { return (i0 > i1) ? _Gcd(i0 , i1) : _Gcd(i1 , i0); }
		public static long Lcm(long i0 , long i1) { return (i0 * i1) / Gcd(i0 , i1); }
		public static long ModPow(long iBaseNumber , long iPow , long iModNumber)
		{
			var num = 1L;
			while(iPow != 0)
			{
				if((iPow & 0x1) != 0)
				{
					num = (num * iBaseNumber) % iModNumber;
				}
				iBaseNumber = (iBaseNumber * iBaseNumber) % iModNumber;
				iPow >>= 1;
			}
			return num;
		}
		public static long CombinationNum(int iLeftNumber , int iRightNumber)
		{
			if(iRightNumber == 0) { return 1; }
			if(iLeftNumber == 0)  { return 0; }
			return iLeftNumber * CombinationNum(iLeftNumber - 1 , iRightNumber - 1) / iRightNumber;
		}

		private static long _Gcd(long i0 , long i1)	{ return (i1 == 0) ? i0 : _Gcd(i1 , i0 % i1); }
	}
}


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

using namespace std;

#define ld long double

// 下凸関数f(x)の[mn, mx]での最小値を与えるxを求める.
ld TernarySearch(ld(*f)(ld), ld mn, ld mx){
    ld e = 1e-10; // 許容誤差
    while (mx - mn > e){
        ld mid_l = (mx / 3) + ((2 * mn) / 3);
        ld mid_r = ((2 * mx) / 3) + (mn / 3);
        if (f(mid_l) >= f(mid_r))
            mn = mid_l;
        else
            mx = mid_r;        
    }
    return mx;
}

int n, k;
vector<pair<ld, ld>> xy;

// (xx, yy)に決定したときのコスト
ld yy;
ld cost(ld xx){
    vector<ld> dist(n);
    for (int i = 0; i < n; ++i){
        ld x_dis = xx - xy[i].first;
        ld y_dis = yy - xy[i].second;
        dist[i] = pow(
            x_dis * x_dis + y_dis * y_dis, 
            0.5
        );
    }
    sort(dist.begin(), dist.end());
    ld cst = 0.0;
    for (int i = n - 1; i >= n - k; --i)
        cst += dist[i];
    return cst;
}

// yを固定したときのcostの最小値を求める.
ld mincost(ld y){
    yy = y;
    return cost(TernarySearch(cost, -1000.0, 1000.0));
}

// 問題を解く.
ld solve(){
    return mincost(TernarySearch(mincost, -1000.0, 1000.0));
}

signed main(){
    cin >> n >> k;
    for (int i = 0; i < n; ++i){
        ld x, y; cin >> x >> y;
        xy.emplace_back(x, y);
    }
    cout << setprecision(10) << solve() << endl;
    return 0;
}


Measured memory_bytes: 3476
import sys
sys.setrecursionlimit(10**9)

MOD = 998244353
N = int(input())
robo = list(list(map(int,input().split()))for i in range(N))
robo.sort()
child = [[]for i in range(N+1)]
stack = [] # 有効、名前

for i in range(N):
    x,d = robo[i]
    while stack and stack[-1][0] <= x:
        stack.pop()
    if stack:
        child[stack[-1][1]].append(i+1)
    else:
        child[0].append(i+1)
    stack.append([x+d,i+1])

def func(x):
    hoge = 1
    for i in child[x]:
        hoge *= func(i)
        hoge %= MOD
    return (hoge + 1) % MOD

print(func(0)-1)


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

const long long mod = 1e9 + 7;

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

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

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

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

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

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

int main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
    return 0;
}


Measured memory_bytes: 3620
N = int(input())
P = [int(input()) for _ in range(N)]
Q = [[0] for _ in range(N)]
for i in range(N):
  Q[P[i] - 1] = i

# print(Q)
  
ans = 1
cnt = 1
for i in range(N - 1):
  if Q[i + 1] > Q[i]:
    cnt += 1
    ans = max(ans, cnt)
  else:
    cnt = 1
    
print(N - ans)

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

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,n) for(int i=1;i<=(int)(n);i++)
#define rep3(i,n) for(int i=0;i<=(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
#define repll(i,n) for(ll i=0;i<(ll)(n);i++)
#define repll2(i,n) for(ll i=1;i<=(ll)(n);i++)
#define REPLL(i,m,n) for(ll i=m;i<(ll)(n);i++)
#define INF (int)1e9  //
#define LINF (ll)4e18  //
#define MOD (int)(1e9)+7
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define PI 3.1415926535898

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

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

    int four = 0;
    int two = 0;

    rep(i, n) {
        int a;
        cin >> a;
        if (a % 4 == 0) {
            four++;
        } else if (a % 2 == 0) {
            two++;
        }
    }
    int k=0;
    if(two !=0) k=1;
    if(four==0) Yes(two==n);
    else Yes(four+1>=n-four-two+k);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main() {
  int n, a, i, max = -1000000, min = 1000000;
  long long sum = 0;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &a);
    if (max < a) {
      max = a;
    }
    if (min > a) {
      min = a;
    }
    sum += a;
  }
  printf("%d %d %lld\n", min, max, sum);
  return 0;
}

Measured memory_bytes: 600
from functools import lru_cache
n = int(input())

def variety(n, arr) :
    ms = set()
    for a in range(n) :
        ms |= count(a+1, arr)
    return(ms)

@lru_cache(maxsize=36)
def count(n, arr) :
    if n == 1 :
        return set(arr)
    else :
        ms = set()
        for a in arr :
            for m in count(n-1, arr) :
                m2 = int(str(a)+str(m))
                ms.add(m2)
        return ms

mylist = list(variety(9, (7, 5, 3))\
            - variety(9, (7, 5))\
            - variety(9, (5, 3))\
            - variety(9, (3, 7)))

print(len([1 for i in mylist if i <= n]))

Measured memory_bytes: 8116
n = int(input())
a = []
for i in range(n):
  d1,d2 = map(int,input().split())
  a.append((d1,d2))
ok = False
for i in range(n-2):
  x,y,z = a[i],a[i+1],a[i+2]
  if x[0]==x[1] and y[0]==y[1] and z[0]==z[1]:
    ok = True
    break
print("Yes" if ok else "No")

Measured memory_bytes: 9200
#include <bits/stdc++.h>
using namespace std;
 
int64_t luca(int x){
  
  vector<int64_t> vec(100, 0);
  vec.at(0) = 2;
  vec.at(1) = 1;
  for(int i = 0; i < x; i++){
    vec.at(i + 2) = vec.at(i + 1) + vec.at(i);
  }
  
  return vec.at(x);
}

int main(){
  int x;
  cin >> x;
  
  cout << luca(x) << endl;
}


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

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

//INT_MAX	2,147,483,647 = 2*1.0e9

const ll INF = 1LL << 60;

ll h[100010];
ll cost[100010];

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

  rep(i, N) cin >> h[i];
  rep(i, N) cost[i] = INF;
  cost[0] = 0;

  for(int i = 1; i < N; i++){
    for(int k = 1; k <= K; k++){
      if(i-k >= 0){
        chmin(cost[i], cost[i-k] + abs(h[i]-h[i-k]));
      }
    }
  }

  cout << cost[N-1] << endl;
  return 0;
}



Measured memory_bytes: 1792
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#define R register
#define Max(_A, _B) (_A > _B ? _A : _B)
#define Min(_A, _B) (_A < _B ? _A : _B)

const long long Inf = 1ll << 55;
int n, k, a[500010], b[500010], l[500010], r[500010], rr[1500010];
long long v[1 << 22], t[1 << 22];
void Pd(int u, R int begin, R int end)
{
	if(~t[u])
	{
		R int mid = begin + end >> 1;
		v[u << 1] = t[u] - rr[mid];
		t[u << 1] = t[u];
		v[u << 1 | 1] = t[u] - rr[end];
		t[u << 1 | 1] = t[u];
		t[u] = -1;
	}
}
void Pu(R int u){ v[u] = Min(v[u << 1], v[u << 1 | 1]); }
long long Query(R int u, R int begin, R int end, R int l, R int r)
{
	if(l <= begin && end <= r) return v[u];
	Pd(u, begin, end);
	R int mid = begin + end >> 1; R long long t1 = Inf, t2 = Inf;
	if(l <= mid) t1 = Query(u << 1, begin, mid, l, r);
	if(r > mid) t2 = Query(u << 1 | 1, mid + 1, end, l, r);
	Pu(u);
	return Min(t1, t2);
}
void Modify(R int u, R int begin, R int end, R int l, R int r, R long long val)
{
	if(l > r) return ;
	if(l <= begin && end <= r)
	{
		v[u] = val - rr[end];
		t[u] = val;
		return ;
	}
	Pd(u, begin, end);
	R int mid = begin + end >> 1;
	if(l <= mid) Modify(u << 1, begin, mid, l, r, val);
	if(r > mid) Modify(u << 1 | 1, mid + 1, end, l, r, val);
	Pu(u);
}
long long GetAns(R int u, R int begin, R int end)
{
	if(begin == end || ~t[u]) return v[u] + rr[end];
	R int mid = begin + end >> 1;
	R long long t1 = Inf, t2 = Inf;
	t1 = GetAns(u << 1, begin, mid);
	t2 = GetAns(u << 1 | 1, mid + 1, end);
	return Min(t1, t2);
}
void Init(R int u, R int begin, R int end)
{
	t[u] = -1; v[u] = -rr[end];
	if(begin == end) return ;
	R int mid = begin + end >> 1;
	Init(u << 1, begin, mid);
	Init(u << 1 | 1, mid + 1, end);
}
int *d[1500010], tot, cnt; 
bool cmp(R int *i, R int *j){ return *i < *j; }
int main()
{
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; ++i) scanf("%d %d", &a[i], &b[i]);
	R long long sum = 0;
	for(int i = 1; i <= n; ++i)
	{
		sum += a[i];
		if(b[i] == 1)
		{
			if(a[i] << 1 > k){ puts("-1"); return 0; }
			r[++cnt] = (k - (sum << 1) % k) % k;
			l[cnt] = (k - ((sum - a[i]) << 1) % k) % k;
		}
	}
	for(int i = 1; i <= n; ++i) d[++tot] = &r[i], d[++tot] = &l[i];
	a[n + 1] = k - 1; d[++tot] = &a[n + 1];
	a[n + 2] = 0; d[++tot] = &a[n + 2];
	std::sort(d + 1, d + 1 + tot, cmp);
	R int hhh = 0, last = -1;
	for(int i = 1; i <= tot; ++i) 
		if(*d[i] != last){ rr[++hhh] = last = *d[i]; *d[i] = hhh; }
		else *d[i] = hhh;
	Init(1, 1, hhh);
	for(int i = 1; i <= cnt; ++i)
	{
		if(l[i] > r[i])
		{
			R long long t = Query(1, 1, hhh, r[i] + 1, l[i]) + rr[l[i]];
			Modify(1, 1, hhh, r[i] + 1, l[i] - 1, Inf);
			Modify(1, 1, hhh, l[i], l[i], t);
		}
		else
		{
			R long long t1 = Query(1, 1, hhh, 1, l[i]) + rr[l[i]];
			R long long t2 = Query(1, 1, hhh, r[i] + 1, hhh) + rr[l[i]] + k;
			Modify(1, 1, hhh, 1, l[i] - 1, Inf);
			Modify(1, 1, hhh, r[i] + 1, hhh, Inf);
			Modify(1, 1, hhh, l[i], l[i], Min(t1, t2));
		}
	}
	printf("%lld\n", GetAns(1, 1, hhh) + (sum << 1));
	return 0;
}

Measured memory_bytes: 20224
#include<iostream>
#include<string>
using namespace std;
int main(){
  int a[30] = {0};
  string s;
  cin >> s;
  for ( int i = 0; i < s.size(); i++ ){
    if(a[s[i] - 'a'] == 0){
      a[s[i] - 'a']++;
    }else{
      cout << "no" << endl;
      return 0;
    }
  }
  cout << "yes" << endl;
}

Measured memory_bytes: 256
a,b,c=map(int,input().split())
d=list(map(int,input().split()))
e=[]
total2=0
for i in range(a):
    e.append(list(map(int,input().split())))
for i in range(a):
    total=0
    for j in range(b):
        total+=d[j]*e[i][j]
    if total+c>0:
        total2+=1
print(total2)

Measured memory_bytes: 9200
S = input()
dp = [[0,0,0,0] for k in range(len(S)+1)]
dp[0][0] = 1
m = 1000000007

for k in range(len(S)):
    if S[k] == "?":
        dp[k+1][0] += (dp[k][0]*3)%m
        dp[k+1][1] += (dp[k][1]*3)%m
        dp[k+1][2] += (dp[k][2]*3)%m
        dp[k+1][3] += (dp[k][3]*3)%m
    else:
        dp[k+1][0] += dp[k][0]
        dp[k+1][1] += dp[k][1]
        dp[k+1][2] += dp[k][2]
        dp[k+1][3] += dp[k][3]
    if S[k] == "A" or S[k] == "?":
        dp[k+1][1] += dp[k][0]
    if S[k] == "B" or S[k] == "?":
        dp[k+1][2] += dp[k][1]
    if S[k] == "C" or S[k] == "?":
        dp[k+1][3] += dp[k][2]
    dp[k+1][0] %= m
    dp[k+1][1] %= m
    dp[k+1][2] %= m
    dp[k+1][3] %= m

print(dp[-1][3])

Measured memory_bytes: 27640
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << "debug " << x << endl;
#define INF (1 << 29)
using namespace std;

int main(){
    string s;
    map<char, int> m;
    bool c = true;
    cin >> s;
    rep(i,s.size()){
        m[s[i]]++;
    }
    for(auto it : m){
        if(it.second % 2 != 0) c = false;
    }
    if(c) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int main(){
   int X,N;
   cin>>X>>N;
   vector<int>A(N);
   vector<bool>answer(300);
   if(N!=0){
   for(int i=0; i<N; i++){
       cin>>A.at(i);
       answer.at(101+A.at(i)-1)=true;
   }
   for(int i=0; i<104; i++){
    if(answer.at(101+X-i-1)==false){
        cout<<X-i<<endl;
        break;
    }
    else if(answer.at(101+X+i-1)==false)
    {
        cout<<X+i<<endl;
        break;
    }
    
   }
   }
   else
   cout<<X<<endl;
}


Measured memory_bytes: 3628
#include <iostream>

using namespace std;

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


Measured memory_bytes: 3088
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>

#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using lint = long long;

int main(void)
{
	lint N;
	cin >> N;
	lint ans = 0;
	ans = (N)*(N - 1) / 2;
	cout << ans << endl;
	return 0;
}


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

const int mod = 1000000007;
struct mint {
	ll x; // typedef long long ll;
	mint(ll x=0):x((x%mod+mod)%mod){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const mint a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint a) const {
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint a) const {
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint a) const {
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}
	
	// for prime mod
	mint inv() const {
		return pow(mod-2);
	}
	mint& operator/=(const mint a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint a) const {
		mint res(*this);
		return res/=a;
	}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint power(ll x, ll n) {
	mint ret = 1;
	while(0 < n){
		if((n % 2) == 0){
			x *= x;
			n >>= 1;
		}else{
			ret *= x;
			--n;
		}
	}
	return ret;
}

vector<pair<ll, int>> prime_factorization(ll n) {
	vector<pair<ll, int>> res;
	for(ll i = 2; i * i <= n; i++){
		if(n % i) continue;
		res.emplace_back(i, 0);
		while(n % i == 0){
			n /= i;
			res.back().second++;
		}
	}
	if(n != 1) res.emplace_back(n, 1);
	return res;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	map<int, int> m;
	vector<map<int, int>> A(n);
	rep(i, n) {
		auto now = prime_factorization(a[i]);
		
		for(auto t: now) {
			int x = t.first;
			int p = t.second;
			A[i][x] = p;
			if(m[x] < p) m[x] = p;
		}
	}
	mint ans = 0;
	mint mx = 1;
	for(auto t: m) {
		int x = t.first;
		int p = t.second;
		mx *= power(x, p);
	}
	
	rep(i, n) {
		mint tmp = mx;
		for(auto t: A[i]) {
			int x = t.first;
			int p = t.second;
			// rep(j, m[x]-A[i][x]) tmp *= x;
			tmp /= power(x, p);
		}
		// cout << tmp << endl;
		ans += tmp;
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3072