akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<complex>
#define EPS 1e-10
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQP(a,b) (EQ((a).real(),(b).real()) && EQ((a).imag(),(b).imag()))
using namespace std;

typedef complex<double> P;

double dot(P a,P b){return real(conj(a)*b);}
double cross(P a,P b){return imag(conj(a)*b);}
double area(P a,P b,P c){return abs(cross(b-a,c-a)/2);}
bool para(P a1,P a2,P b1,P b2){return abs(cross(a1-a2,b1-b2))<EPS;}
bool is_cp(P a1,P a2,P b1,P b2){
  if(cross(a2-a1,b1-a1) * cross(a2-a1,b2-a1) < EPS)
    if(cross(b2-b1,a1-b1) * cross(b2-b1,a2-b1) < EPS)return true;
  return false;
}
P seg_cp(P a1,P a2,P b1,P b2){
  b2-=b1;
  double d = abs(cross(b2,a1-b1));
  return a1 + (a2-a1)*d/( d + abs(cross(b2,a2-b1)) );
}

int main(){
  P p11,p12,p21,p22,p31,p32;

  for(;;){
    cin >> p11.real() >> p11.imag() >> p12.real() >> p12.imag();
    if(!abs(p11) && !abs(p12))break;
    cin >> p21.real() >> p21.imag() >> p22.real() >> p22.imag();
    cin >> p31.real() >> p31.imag() >> p32.real() >> p32.imag();

    if(para(p11,p12,p21,p22) || para(p21,p22,p31,p32) || para(p31,p32,p11,p12))
      cout << "kyo\n";
    else if(!is_cp(p11,p12,p21,p22) || !is_cp(p21,p22,p31,p32) || !is_cp(p31,p32,p11,p12))
      cout << "kyo\n";
    else{
      P cp1 = seg_cp(p11,p12,p21,p22);
      P cp2 = seg_cp(p21,p22,p31,p32);
      P cp3 = seg_cp(p31,p32,p11,p12);
      if(EQP(cp1,cp2))cout << "kyo\n";
      else{
	double s = area(cp1,cp2,cp3);
	if(s+EPS>1900000)cout << "dai-kichi\n";
	else if(s+EPS>1000000)cout << "chu-kichi\n";
	else if(s+EPS>100000)cout << "kichi\n";
	else cout << "syo-kichi\n";
      }
    }
    
  }
}

Measured memory_bytes: 0
n, m = map(int, input().split())

def bellman_ford(s):
    d = [float('inf')] * n
    d[s] = 0
    # 注意点として、閉路を探索(=スコアが更新されたか確かめる)ためにn*2回実行する必要がある
    for i in range(n*2):
        for edge in g:
            if edge[0] != float('inf') and d[edge[1]] > d[edge[0]] + edge[2]:
                d[edge[1]] = d[edge[0]] + edge[2]
                if i>=n-1 and edge[1] == n-1:
                    return -1
    return d

g = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    c *= -1
    g.append([a,b,c])

ret = bellman_ford(0)

if isinstance(ret, list):
    print(-1 * ret[n-1])
else:
    print('inf')



Measured memory_bytes: 3316
#include <iostream>
#include <cstring>
#include<vector>
#include <algorithm>
#include<cstdlib>
#include<set>
#include<math.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<n;i++)

int main()
{
	set<ll> a,b;
	ll n, k;
	cin >> n >> k;
	ll  count, p;
	count = 0;
	vector<vector<ll>> v(k,vector<ll>());
	vector<ll> d(k);
	rep(i, k)
	{
		cin >> d[i];
		v[i].resize(d[i]);

		rep(t, d[i])
		{
			cin >> v[i][t];
		}
	}
	vector<bool> tf(n);
	rep(x, n)
	{
		rep(p, k)
		{
			rep(q, d[p])
			{
				if (v[p][q] == x + 1)
				{
					tf[x] = true;
				}
			}
		}
	}
	
	rep(y, n)
	{
		if (tf[y])
		{
			count++;
		}
	}

	cout << n - count << "\n";
	return 0;
}

Measured memory_bytes: 3624
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N = 10**9 +7

S = int(input())
if S==1 or S==2:
    print(0)
    exit(0)

n = S // 3
ans =0
for i in range(1, n+1):
    m = S - 2 * i
    ans += cmb(m-1,i-1)

print(ans%N)

Measured memory_bytes: 9620
#include <stdio.h>

int main(void)
{
	int i, j;
	int a = 0;
	int b = 0;
	int c;
	int n, m, x;

	scanf("%d%d%d", &n, &m, &x);
	
	for  (i = 0; i < m; i++){
		scanf("%d", &c);
		if (x < c){
			b++;
		}else{
			a++;
		}
	}
	
	if (a < b){
		printf("%d", a);
	}else{
		printf("%d", b);
	}

	return 0;
}

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

using Int = unsigned long long;
using namespace std;

#define ARC(i, a, b) for(Int i = (a); i < (b); ++i)
#define RC(i, n) ARC(i, 0, n)
#define ARCH(i, a, b) for(Int i = (a) - 1; i >= (b); --i)
#define RCH(i, n) ARCH(i, n, 0)
template<class T> T ant(const T &a, const T &b){ return a > b ? a : b; };
template<class T> T ont(const T &a, const T &b){ return a < b ? a : b; };
template<class T> T th(T &a, const T &b, T (*f)(const T &, const T &)){ a = f(a, b); }
#define anth(a, b) th(a, b, ant)
#define onth(a, b) th(a, b, ont)

int main(){
	Int n, a, b;
	cin >> n >> a >> b;
	Int ans = n / (a + b) * a;
	ans += ont(n % (a + b), a);
	cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;


public class Main {

    private static final int INF = 1000000007;
    private static final int INF1 = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int a = n / (2*d + 1);
        int mod = n % (2*d + 1);
        if(mod != 0){
            a += 1;
        }
        System.out.println(a);
    }
}


Measured memory_bytes: 21844
/*
  ∧,,∧
( 'ω' )つ ＜WA,またお前か！！　
（m9 ＼ 　　
　 ＼　 ＼
　 　 ) ) ＼
　 ／／ ＼ ＼
　 (＿） 　 (＿)
*/

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

#define all(x) (x).begin(),(x).end()
#define rep(x, y) for (int x = 0; x < y; x++)
#define MOD 1000000007

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

ostringstream oss_global;
string s_global = oss_global.str();

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

    LL ans = (LL)N*(N-1)/2;
    cout << ans << endl;
    return 0;
}


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

#define SIZE_OF_ARRAY(array) sizeof(array)/sizeof(array[0])



int main() {
    int K;
    cin >> K;
    std::queue<long long> q;
    for(long long i = 1; i<= 9; i++){
        q.push(i);
    }
    long long b;
    for(int k = 0; k < K; k++){
        b = q.front();
        long long mod = b%10;
        q.pop();
        if(mod != 0){
            q.push(10*b + mod - 1);
        }
        q.push(10*b + (b%10));
        if(mod != 9){
            q.push(10*b + mod + 1);
        }
    }
    cout << b;
}

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

int main(){
    int n;
    cin >> n;
    int curMin = 100000;
    
    for (int i = 0; i < n - 1; i++){
        int a = i + 1;
        int b = n - a;
        int sumA = 0;
        int sumB = 0;
        while (a > 0){
            sumA += a % 10;
            a /= 10;
        }
        while (b > 0){
            sumB += b % 10;
            b /= 10;
        }
        curMin = min(curMin, sumA + sumB);
        
    }

    cout << curMin << endl;
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    int m, k; cin >> m >> k;

    if (k == 0) {
        for (int i = 0; i < (1 << m); i++) {
            cout << i << ' ' << i << " \n"[i==(1<<m)-1];
        }
    } else if (m == 1) {
        cout << "-1" << '\n';
    } else if (k < (1 << m)) {
        cout << 0 << ' ';
        for (int i = 1; i < (1 << m); i++) {
            if (i == k) continue;
            cout << i << ' ';
        }
        cout << 0 << ' ' << k << ' ';
        for (int i = (1 << m) - 1; i >= 1; i--) {
            if (i == k) continue;
            cout << i << ' ';
        }
        cout << k << '\n';
    } else {
        cout << "-1" << '\n';
    }
    return 0;
}

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

long long bp(long long i, int j){
    if(i){
       if(i+1>=pow(2, j+1))
       {
           if(i+3==pow(2, j+2)) return pow(2, j+1)-1;
           else return pow(2, j)+bp(i-pow(2, j+1)+1, j-1);
       }
       else return bp(i-1, j-1);
    }
    else return 0;
}

int main() {
	int N;
	long long X;
    cin >> N >> X;
    cout << bp(X, N) << endl;
    return 0;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : (-1 * (a)))
#define rep(i, n) for ((i) = 0; (i) < (int)(n); (i)++)
#define rep2(i, s, e) for ((i) = (s); (i) < (int)(e); (i)++)

void arg_marge(int *, int *, int);

int main(void)
{

    int h, n, i, j;
    int *a, *a2, *b, *b2, *ab, *c;
    int *dp, *dp2;

    scanf("%d %d", &h, &n);
    a = (int *)malloc(n * sizeof(int));
    b = (int *)malloc(n * sizeof(int));
    a2 = (int *)malloc(n * sizeof(int));
    b2 = (int *)malloc(n * sizeof(int));
    ab = (int *)malloc(n * sizeof(int));
    c = (int *)malloc(n * sizeof(int));
    rep(i, n)
    {
        scanf("%d %d", a2 + i, b2 + i);
        ab[i] = (h * b2[i]) / a2[i];
        c[i] = i;
    }
    arg_marge(ab, c, n);
    rep(i, n)
    {
        a[i] = a2[c[i]];
        b[i] = b2[c[i]];
    }
    free(a2);
    free(b2);
    free(ab);
    free(c);
    int mx = ((h / a[0] + 1) * b[0]) + 1;
    dp = (int *)malloc(mx * sizeof(int));
    dp2 = (int *)malloc(mx * sizeof(int));
    rep(i, mx)
    {
        dp[i] = 0;
        dp2[i] = 0;
    }
    //rep(j, mx) printf("%d ", dp[j]);
    rep(i, n)
    {
        //printf("\n");
        rep(j, b[i]) dp2[j] = dp[j];
        rep2(j, b[i], mx)
        {
            dp2[j] = max(dp2[j - b[i]] + a[i], dp[j]);
            //if (dp2[j] >= h)
            //{
            //    printf("break\n");
            //    mx = i + 1;
            //    break;
            //}
        }
        rep(j, mx) dp[j] = dp2[j];
        //rep(j, mx) printf("%d ", dp[j]);
    }
    rep(i, mx) if (dp[i] >= h) break;
    printf("%d", i);
}

void arg_marge(int *a, int *b, int n)
{

    if (n == 1)
        return;

    int *l2, *r2, *tmp, *arg_l2, *arg_r2, *arg_tmp;
    l2 = (int *)malloc((n / 2) * sizeof(int));
    r2 = (int *)malloc((n - n / 2) * sizeof(int));
    tmp = (int *)malloc((n) * sizeof(int));
    arg_l2 = (int *)malloc((n / 2) * sizeof(int));
    arg_r2 = (int *)malloc((n - n / 2) * sizeof(int));
    arg_tmp = (int *)malloc((n) * sizeof(int));

    for (int i = 0; i < n / 2; i++)
    {
        l2[i] = a[i];
        arg_l2[i] = b[i];
    }
    for (int i = 0; i < n - n / 2; i++)
    {
        r2[i] = a[i + n / 2];
        arg_r2[i] = b[i + n / 2];
    }

    arg_marge(l2, arg_l2, n / 2);
    arg_marge(r2, arg_r2, n - n / 2);

    for (int i = 0; i < n / 2; i++)
    {
        tmp[i] = l2[i];
        arg_tmp[i] = arg_l2[i];
    }
    for (int i = n / 2; i < n; i++)
    {
        tmp[i] = r2[n - i - 1];
        arg_tmp[i] = arg_r2[n - i - 1];
    }

    int lp = 0, rp = n - 1, p = 0;
    int l3, r3;
    while (p < n)
    {
        l3 = tmp[lp];
        r3 = tmp[rp];
        if (l3 < r3)
        {
            a[p] = l3;
            b[p] = arg_tmp[lp];
            lp++;
            p++;
        }
        else
        {
            a[p] = r3;
            b[p] = arg_tmp[rp];
            rp--;
            p++;
        }
    }

    return;
}


Measured memory_bytes: 781440
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
#define REP(i,n) for (int i=0; i<n; i++)
#define ADD(a,b,c) "("+ a +" "+ c +" "+ b +")"
 
string i2s(int n){
  stringstream ss;
  ss << n;
  return ss.str();
}
 
int op(int x, int y, int mode){
    switch (mode){
    case 0:
        return x+y;
    case 1:
        return x-y;
    case 2:
        return x*y;
    }
}
 
string check(int x[], int n){
    int x0=x[0], x1=x[1], x2=x[2], x3=x[3];
    string s0=i2s(x0), s1=i2s(x1), s2=i2s(x2), s3=i2s(x3);
    string ops="+-*", eq1, eq2;
    int n1 = ops.size();
    REP(i1, n1){
        int a1 = op(x0, x1, i1);
        eq1 = ADD(s0, s1, ops[i1]);
        REP(i2, n1){
            int a2 = op(a1, x2, i2);
            eq2 = ADD(eq1, s2, ops[i2]);
            REP(i3, n1)
                if (op(a2, x3, i3)==n) return ADD(eq2, s3, ops[i3]);
            a2 = op(x2, x3, i2);
            eq2 = ADD(s2, s3, ops[i2]);
            REP(i3,n1)
                if (op(a1, a2, i3)==n) return ADD(eq1,eq2,ops[i3]);
        }
    }
    return "";
}
 
int f0041(){
    int n=10, x[4];
    while (cin>>x[0]>>x[1]>>x[2]>>x[3]){
        if (x[0]==0 && x[1]==0 && x[2]==0 && x[3]==0) return 0;
 
        sort(x,x+4);
        bool f = true;
        do{
            string s = check(x, n);
            if (s != ""){
                cout<<s<<endl;
                f = false;
                break;
            }
        }while (next_permutation(x,x+4));
        if (f) cout<<"0"<<endl;
    }
}
 
int main(void){
    f0041();
}

Measured memory_bytes: 1248
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define MOD (ll)1000000007

int main(void)
{
	char s[4];
	scanf("%s", s);
	int ans = 0;
	int temp = 0;
	for (int i = 0; i < 3; i++)
		if (s[i] == 'R')
			temp++;
		else
			ans = max(ans, temp), temp = 0;
	ans = max(ans, temp);
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 1728
def a_xor_circle(N, A):
    """
    N枚の帽子のそれぞれには整数 a_i が書かれている。
    円環状に並んだN頭のラクダのそれぞれに1枚ずつ帽子を被せたい。
    どのラクダについても以下の条件が成立するような帽子の被せ方が存在するか判定せよ。
    ・両隣のラクダが被っている帽子に書かれた数のbitwise-xorが自身の被る帽子の値と等しい

    条件より、x_{i+1} = x_i ^ x_{i+2} で、両辺に x_{i+1} との排他的論理和を取ると
    x_i ^ x_{i+1} ^ x_{i+2} = 0 が成立する。同じことをして、
    x_{i+1} ^ x_{i+2} ^ x_{i+3} = 0 が成立する。この2つの式の両辺それぞれ
    排他的論理和を取ると、 x_i ^ x_{i+3} = 0 すなわち x_i = x_{i+3} である。
    だから、以下の場合、条件を満たす被せ方がある。
    ・全部の帽子の数が0 (この場合、ラクダの数は関係ない)
    ・xが書かれた帽子 : 0が書かれた帽子 = 2 : 1 (x, x, 0 を並べる)
    ・x^y^z=0 となる相異なる3整数が 1:1:1 の割合 (x, y, z を並べる)
    """
    from collections import Counter
    num_count = Counter(A)
    if len(num_count) == 1:
        return 'Yes' if num_count[0] != 0 else 'No'
    elif len(num_count) == 2:
        if num_count[0] == 0:
            return 'No'
        for k, v in num_count.items():
            if k == 0:
                count_zero = v
            else:
                count_other = v
        return 'Yes' if count_other == 2 * count_zero else 'No'
    elif len(num_count) == 3:
        x, y, z = num_count.keys()
        count_x, count_y, count_z = num_count.values()
        if x ^ y ^ z != 0:
            return 'No'
        if count_x != count_y or count_y != count_z or count_z != count_x:
            return 'No'
        return 'Yes'
    else:
        return 'No'
    return None

N = int(input())
A = [int(i) for i in input().split()]
print(a_xor_circle(N, A))

Measured memory_bytes: 14212
for i in range (50):
    m,f,r = list(map(int,input().split()))
    if [m,f,r] == [-1,-1,-1]:
        break
    else:
        if m == -1 or f == -1:
            print("F")
        elif m + f >= 80:
            print("A")
        elif m + f >= 65:
            print("B")
        elif m + f >= 50:
            print("C")
        elif m + f >= 30:
            if r >= 50:
                print("C")
            else:
                print("D")
        else:
            print("F")


Measured memory_bytes: 5600
#include<stdio.h>
int main()
{
  int a,b,c,d;
  scanf("%d",&a);
  b=a/100;
  c=(a-b*100)/10;
  d=a%100-c*10;
   if(d==7)
   {
     printf("Yes");
   }
else if(c==7)
{
  printf("Yes");
}
  else if(b==7)
  {
    printf("Yes");
  }
  else if (d==7)
  {
    printf("Yes");
  }
  else
  {
    printf("No");
  }
  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <algorithm>
using namespace std ;
using ll = long long ;

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

int main(){
	int n ; cin >> n ;
	ll ans = 1 ;
	for(int i=0;i<n;i++){
		ll t ; cin >> t ;
		ans = lcm(ans,t) ;
	}
	cout << ans << endl ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
signed main(){
    int a , b , c , d , x , y;
    cin >> a >> b >> c >> d;
    
    x = c / b;
    if(c%b > 0){
        x ++ ;
    } 
    
    y = a / d;
    if(a%d > 0){
        y ++;
    }
    
    if(x <= y){
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    
    return(0);
}

Measured memory_bytes: 3636
#include <iostream>

using namespace std;

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

  int p[n];
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }

  long long max = 0;
  for (int i = 0; i < k; i++) {
    max += p[i];
  }

  long long temp = max;
  for (int i = 0; i < n - k; i++) {
    temp += (p[i + k] - p[i]);
    if (temp > max) {
      max = temp;
    }
  }

  if ((max + k) % 2 == 0) {
    cout << (max + k) / 2 << endl;
    return 0;
  } else {
    string ans = to_string((max + k) / 2);
    ans += ".5";
    cout << ans << endl;
    return 0;
  }
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
int main(){
	int A, B, H, M;
	scanf("%d %d %d %d", &A, &B, &H, &M);	
	long double h = M_PI * (H + M / 60.0) / 6.0, m = M_PI * M / 30.0;
	printf("%.10Lf\n", sqrtl((long double)A * A + (long double)B * B - 2.0 * A * B * cosl(h - m)));
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2524
#!/usr/bin/perl
use POSIX qw(floor);

my ($a,$v) = map { $_ - 0 } split(/\s+/,<STDIN>);
my ($b,$w) = map { $_ - 0 } split(/\s+/,<STDIN>);
my ($t) = map { $_ - 0 } split(/\s+/,<STDIN>);

my $d = abs($a-$b);

if( $d == 0 ){
  print "YES\n"; exit(0);
}

if( $v <= $w ){
  print "NO\n"; exit(0);
}

if( $t * ($v - $w) >= $d ){
  print "YES\n"; exit(0);
}
print "NO\n";




Measured memory_bytes: 6660
from inspect import currentframe


def debug_print(s):
    # print(s)
    return


def debug_key(*args):
    names = {id(v): k for k, v in currentframe().f_back.f_locals.items()}
    debug_print(', '.join(names.get(id(arg), '???')+' = '+repr(arg) for arg in args))


def solve(S):
    N = len(S)
    ans = 0

    for i in range(2 ** (N - 1)):
        culculate = S[0]
        for j in range(N - 1):
            if i & (1 << j):
                culculate += "+" + S[j + 1]
            else:
                culculate += S[j + 1]
        ans += eval(culculate)
        debug_key(culculate)
    print(ans)


if __name__ == '__main__':

    S_input = input()

    solve(S_input)



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

#define ll long long
#define ull unsigned long long

using namespace std;

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

	vector<vector<int>> tree(N, vector <int>());
	for (int ii = 0; ii < N-1; ++ii){
		int a, b;
		cin >> a >> b;
		a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	//各頂点を色分けする
	queue<int> q;
	int initIdx = 0;
	q.push(initIdx);	//最初のキューを追加

	vector<int> dist(N, -1);
	dist[initIdx] = 0;
	int even = 1;
	int odd = 0;
	while (!q.empty()) {
		int idx = q.front();
		q.pop();
		for (int ii = 0; ii < tree[idx].size(); ++ii){
			int idx2 = tree[idx][ii];
			if (dist[idx2] == -1){
				dist[idx2] = dist[idx] + 1;
				if (dist[idx2] % 2 == 0){
					even++;
				} else {
					odd++;
				}
				q.push(idx2);
			}
		}
	}
	assert(even + odd == N);

	vector <int> seq(N, 0);
	int tmp1 = 1;
	int tmp2 = 2;
	int tmp3 = 3;
	if (even <= N / 3){
		//evenの頂点に3の倍数を割り振る（ほかは適当）
		for (int ii = 0; ii < N; ++ii){
			if (dist[ii] % 2 == 0){
				seq[ii] = tmp3;
				tmp3 += 3;
			}
		}
		for (int ii = 0; ii < N; ++ii){
			if (dist[ii] % 2 != 0){
				if (tmp3 <= N){
					seq[ii] = tmp3;
					tmp3 += 3;
				} else if (tmp2 <= N) {
					seq[ii] = tmp2;
					tmp2 += 3;
				} else {
					seq[ii] = tmp1;
					tmp1 += 3;					
				}
			}
		}
	} else if (odd <= N / 3) {
		//oddの頂点に3の倍数を割り振る（ほかは適当）
		for (int ii = 0; ii < N; ++ii){
			if (dist[ii] % 2 != 0){
				seq[ii] = tmp3;
				tmp3 += 3;
			}
		}
		for (int ii = 0; ii < N; ++ii){
			if (dist[ii] % 2 == 0){
				if (tmp3 <= N){
					seq[ii] = tmp3;
					tmp3 += 3;
				} else if (tmp2 <= N) {
					seq[ii] = tmp2;
					tmp2 += 3;
				} else {
					seq[ii] = tmp1;
					tmp1 += 3;					
				}
			}
		}
	} else {
		//evenの頂点x==1 mod 3を，oddの頂点にx==2 mod 3を割り振る（ほかは適当）
		for (int ii = 0; ii < N; ++ii){
			if (dist[ii] % 2 != 0){
				if (tmp1 <= N){
					seq[ii] = tmp1;
					tmp1 += 3;
				} else if (tmp3 <= N) {
					seq[ii] = tmp3;
					tmp3 += 3;
				} else {
					seq[ii] = tmp2;
					tmp2 += 3;					
				}
			} else {
				if (tmp2 <= N){
					seq[ii] = tmp2;
					tmp2 += 3;
				} else if (tmp3 <= N) {
					seq[ii] = tmp3;
					tmp3 += 3;
				} else {
					seq[ii] = tmp1;
					tmp1 += 3;
				}
			}
		}
	}

	for (int ii = 0; ii < N; ++ii){
		cout << seq[ii] << " ";
	}

	return 0;
}


Measured memory_bytes: 15220
#define deb 123321
#define fi first
#define se second
#define mp make_pair
#define pb push_back

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

typedef long long ll;
typedef unsigned long long ull;
constexpr int R=5e7+69, INF=2e9+6969;

int a,b;

int main()
{
	scanf("%d%d", &a, &b);
	printf("%d\n", a*b);
	return 0;
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
using namespace std;
using v = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}

void chturn(char c, int *turn){
    switch(c){
        case 'a':
            *turn = 0; break;
        case 'b':
            *turn = 1; break;
        case 'c':
            *turn = 2; break;
    }
}
int main(int argc, char *argv[]){
//     string sa, sb, sc; cin >> sa >> sb >> sc;
//     int a, b, c; a = b = c = 0;
//     int turn = 0;
//     char res;
//     // if(sa.size() == 1){ res = 'A'; goto res; }
//     while(1){
//         // cout << turn;
//         switch(turn){
//             case 0:
//                 if(a == sa.size() - 1 || sa.size() == 1){ res = 'A'; goto res; }
//                 a++;
//                 chturn(sa[a], &turn);
//                 break;
//             case 1:
//                 if(b == sb.size() - 1 || sb.size() == 1){ res = 'B'; goto res; }
//                 b++;
//                 chturn(sb[b], &turn);
//                 break;
//             case 2:
//                 if(c == sc.size() - 1 || sc.size() == 1){ res = 'C'; goto res; }
//                 c++;
//                 chturn(sc[c], &turn);
//                 break;
//         }
//     }
// res:
//     cout << res << endl;
    string S[3] = {};
    int p[3] = {};
    int current = 0;
    for(int i = 0; i < 3; i++)cin >> S[i];
    while(true){
        if(p[current] == S[current].length()){
            printf("%c", 'A' + current);
            return 0;
        }else{
            p[current]++;
            current = S[current][p[current]-1]-'a';
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int main() {
    long long A,B,C,D,ans;
    cin>>A>>B>>C,D=max(A,max(B,C));
    if(A%2+B%2+C%2<3) ans=0;
    else if(A==D) ans=B*C;
    else if(B==D) ans=A*C;
    else ans=A*B;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
x,y = input().split()
a = ['1','3','5','7','8','10','12']
b = ['4','6','9','11']
c = ['2']
if a.count(x) > 0:
  x = a
elif b.count(x) > 0:
  x = b
else:
  x = c
if a.count(y) > 0:
  y = a
elif b.count(y) > 0:
  y = b
else:
  y = c
if x == y:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
from sys import stdin
import bisect

N = int(stdin.readline().rstrip())
L = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
L.sort()
for i in range(1, N):
    for j in range(i):
        ans += max(bisect.bisect_left(L, L[i] + L[j]) - i - 1, 0)

print(ans)


Measured memory_bytes: 44476
#include <iostream>
    #include<math.h>
    #include <limits>
    #include <iomanip>
    #include <algorithm>
    using namespace std;
    #define rep(i, n) for (int i =0; i < (int)(n); i++)
     
    int main() {
    	int N;
    	cin >> N;
    	
      if(N<1000)cout<<"ABC"<<endl;
      else cout<<"ABD"<<endl;
     
    return 0;
    } 

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

int main(){
    int ans = 0,m=10;
    for(int i = 0;i < 5;i ++){
        int t;
        cin >> t;
        ans += t;
        if(t%10){
            m = min(m,t%10);
            ans += 10-(t%10);
        }
    }
    ans -= 10-m;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
X,K,D=map(int,input().split())
X=max(X,-X)

mostL=X-K*D
if 0<=mostL:
    print(mostL)
else:
    K-=X//D
    X%=D
    if K%2==1:
        print(abs(X-D))
    else:
        print(X)




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

const ll MOD = 1e+9+7;
const int INF = 1e+9+7;

int main(){
    int N,M,Q;
    cin >> N >> M >> Q;
    int l,r;
    vector<vector<int>> s(N+1,vector<int>(N+1,0));
    vector<vector<int>> c(N,vector<int>(N,0));

    rep(i,M){
        cin >> l >> r;
        l--;
        r--;
        c[l][r]++;
    }
    
    rep(i,N){
        rep(j,N){
            s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+c[i][j];
        }
    }


    vector<int> p(Q),q(Q);
    rep(i,Q){
        cin >> p[i] >> q[i];   
    }

    rep(i,Q){
        l = p[i];
        r = q[i];
        cout << s[r][r] - s[r][l-1] - s[l-1][r] + s[l-1][l-1] << endl;
    }
}


Measured memory_bytes: 3712
# -*- coding: utf-8 -*-
import math
import datetime
import itertools
import sys
import copy

# 入力
#N = int(input())
#S = str(input())
#N, A, B = map(int, input().split())

N, W = map(int, input().split())
H = []
for _ in range(N) :
  H.append(list(map(int, input().split())))
#print(H)

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(1, N+1) :
  for j in range(W+1) :
    dp[i][j] = max(dp[i-1][j], dp[i][j])
    if dp[i-1][j] > 0 and j+H[i-1][0] <= W:
      dp[i][j+H[i-1][0]] = max(dp[i-1][j+H[i-1][0]], dp[i-1][j] + H[i-1][1])
    
  dp[i][H[i-1][0]] = max(dp[i-1][H[i-1][0]], H[i-1][1])
  #print (dp[i])      
#print (dp)

print (max(dp[N][:]))

Measured memory_bytes: 175260
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define MAXN 100005
using namespace std;
typedef long long ll;
int w,n,m;
int s,t,v;
int f[MAXN];
int val[MAXN];
bool flag = 0;
int find(int x)
{
    if (f[x]==x)    return x;
    int F=find(f[x]);val[x]+=val[f[x]];return f[x]=F;
}
void Union(int x,int y,int w)
{
    int a=find(x),b=find(y);
    if (a!=b)   f[a]=b,val[a]=val[y]-val[x]-w;
    else
    if (val[y]-val[x]!=w)   flag=1;
}
int main()
{
    scanf("%d%d",&n,&m);flag=0;
    for (int i=0;i<=n;i++)  f[i]=i,val[i]=0;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s,&t,&v);
        Union(s,t,v);
    }
    printf(flag?"No\n":"Yes\n");
    return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,s[26],L,x,y;
char a;
void f(void){
    int t[26];
    for(int i=0;i<26;i++)t[i]=s[i];
    sort(t,t+26);
    for(int i=0;i<26;i++){
        if(t[25]==s[i])L=i;
    }
    x=t[25],y=t[24];
    return ;
}
int main(void){
    while(1){
    cin>>n;
    if(n==0)return 0;
    for(int i=0;i<26;i++)s[i]=0;
    int ok=1;
    for(int i=0;i<n;i++){
        cin>>a;
        s[a-'A']++;
        f();
        if(x>y+(n-i-1)){
            if(ok){cout<<char('A'+L)<<" "<<i+1<<endl;ok=0;}
        }
    }
    if(ok)cout<<"TIE"<<endl;
    }
}



Measured memory_bytes: 3156
const lines: string[] = [];
const reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
reader.on("line", function (line: string) {
  lines.push(line);
});

reader.on("close", function () {
  const rule = lines.shift().split(" ").map(Number);
  const data: number[] = lines
    .shift()
    .split(" ")
    .map((int) => parseInt(int));

  const dp = data.map(() => Infinity);
  dp[0] = 0;

  for (let i = 1; i < rule[0]; i++) {
    for (let j = i - rule[1]; j < i; j++) {
      if (j >= 0) {
        dp[i] = Math.min(dp[i], dp[j] + abs(data[j] - data[i]));
      }
    }
  }

  console.log(dp[rule[0] - 1]);
});

function abs(val: number) {
  return val < 0 ? -val : val;
}


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

#include <atcoder/all>

// #LIB#

using namespace std;
using namespace atcoder;
using ll = long long;
#define double long double
#define rep(i, n) for (long long i = 0; i < (n); ++i)
#define repr(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(x, c) for (auto&& x : (c))
#define updatemax(t, v) ((t) = std::max((t), (v)))
#define updatemin(t, v) ((t) = std::min((t), (v)))
#ifdef ONLINE_JUDGE
#define endl _endl
const char _endl = (cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout.precision(16), '\n');
#endif

using mint = static_modint<998244353>;

int main() {
  ll n, m;
  cin >> n >> m;
  vector<mint> a(n - 1 - 0 + 1);
  rep(i, n) {
    ll x;
    cin >> x;
    a[i] = x;
  }
  vector<mint> b(m - 1 - 0 + 1);
  rep(i, m) {
    ll x;
    cin >> x;
    b[i] = x;
  }
  auto c = convolution(a, b);
  itr(x, c) cout << x.val() << ' ';
  cout << endl;
}


Measured memory_bytes: 19100
#include<bits/stdc++.h>
using namespace std;
int main()
{   
    long long int sum=0;
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                sum+=__gcd(i,__gcd(j,k));
            }
        }
    }
    cout<<sum;
    return 0;
}  
  

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main(){
 string S;
 cin >> S;
  int max = 0;
  int sum = 0;
  for(int i = 0; i < S.size(); i++){
    if(S.at(i) != 'A' &&S.at(i) != 'C' &&S.at(i) != 'G' &&S.at(i) != 'T') {
  
      if(sum > max ) max = sum;
      sum = 0;
    }
    else{sum++;}
  }
   if(sum > max ) max = sum;
  
  cout << max << endl;
 return 0; 
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int ans = 0;
		for(int i = 0; i <= s.length()-t.length(); i++) {
			int count = 0;
			for(int j = 0; j < t.length(); j++) {
				if(s.charAt(i+j)==t.charAt(j)) {
					count++;
				}
			}
			ans = Math.max(ans, count);
		}
		System.out.println(t.length()-ans);
	}
}

Measured memory_bytes: 35656
#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 1e5 + 10 ;
const ll INF = 1e18 + 10 ;
int n , k ; 
vector<int> v ;
int dp[N] ;
int dfs(int cur){
    if ( cur == 0 ) {
        return 0 ;
    }
    if ( dp[cur] != -1 ) return dp[cur] ;
    bool ans = false ;
    for(int i = 0; i < n; i++){
        if ( v[i] <= cur ){
            if ( not dfs(cur - v[i] ) ){
                ans = true ;
            }
        }
    }
    return dp[cur] = ans ;
}
signed main(){
    fastio
    memset(dp, -1, sizeof dp) ;
    cin >> n >> k ; 
    v = vector<int>(n) ;
    for(int i = 0; i < n; i++){
        cin >> v[i] ;
    }
    int ans = dfs(k) ;
    puts(ans ? "First" : "Second") ;
    return 0; 
}

Measured memory_bytes: 10636
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#include<stdio.h>
#include<functional>
#include<queue>

using ll = long long;

using namespace std;

ll mod = 1000000007;

ll n_pow(ll a, ll n) {
	if (n == 0)return 1;
	ll t = n_pow(a, n / 2);
	t *= t;
	t %= mod;
	if (n % 2 == 1)t *= a;
	return t % mod;
}

const int INF = 1001001001;
//const ll INF = 1e18;

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };

ll cal_gcd(ll a, ll b) {
	ll m = max(a, b);
	ll n = min(a, b);
	while (m%n != 0) {
		ll b = m % n;
		m = n;
		n = b;
	}
	return n;
}


int main() {
	ll a, b, c, k;
	cin >> a >> b >> c >> k;
	int ans = 0;
	if (k <= a) {
		ans = k;
	}
	else {
		ans += a;
		k -= a;
		k -= b;
		if (k > 0)ans -= k;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <stdlib.h>

typedef unsigned long long int uint64;
typedef long long int          int64;
 
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void get_N (int64 *n)
{
  int cnt;
  
  cnt = scanf("%lld", n);

  return;
}

void get_NK (int64 *n, int64 *k)
{
  int cnt;
  
  cnt = scanf("%lld %lld", n, k);

  return;
}

typedef struct _tmp_t {
  int64    a;
  int64    b;
} tmp_t;


int compare_a(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->a > y->a) return 1;
  if (x->a < y->a) return -1;

  return 0;
}

int compare_b(const void *a, const void *b)
{
  tmp_t *x;
  tmp_t *y;

  x = (tmp_t *)a;
  y = (tmp_t *)b;

  if (x->b > y->b) return 1;
  if (x->b < y->b) return -1;

  return 0;
}

void qsort_a (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_a);
}

void qsort_b (tmp_t *array, int size)
{
  qsort(array, size, sizeof(tmp_t), compare_b);
}

char S[10];
int main()
{
  int cnt;

  cnt = scanf("%s", S);

  if (S[0] == 'S') {
    printf("Cloudy");
    return 0;
  }
  if (S[0] == 'C') {
    printf("Rainy");
    return 0;
  }
  if (S[0] == 'R') {
    printf("Sunny");
    return 0;
  }
  return 0;
}



Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }


struct P{ double x, y; };
bool operator > (P x, P y)
{ return x.x > y.x || (x.x == y.x && x.y > y.x); }

double CalcArea(P a, P b, P c)
{
	double A = sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
	double B = sqrt(pow(b.x - c.x, 2.0) + pow(b.y - c.y, 2.0));
	double C = sqrt(pow(c.x - a.x, 2.0) + pow(c.y - a.y, 2.0));
    
	double s = (A + B + C) / 2;
    
	return sqrt(s * (s - A) * (s - B) * (s - C));
}


int main()
{
	vector<P> points;

	P in;
	char k;
	while(cin >> in.x >> k >> in.y && in.x != -100)
		points.push_back(in);

	double S = 0;
	REP(i, 1, points.size()-1)
		S += CalcArea(points[0], points[i], points[i + 1]);

	cout << setprecision(10) << S << endl;
}

Measured memory_bytes: 0
/*input
8 3
7 3 1 8 4 6 2 5
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 100900
#define INF 0x3f3f3f3f

int n , x[MAX] , idx , m;
int32_t main(){
	IOS;
	cin >> n >> m;
	cout << (n - 1) / (m - 1) + ((n - 1) % (m - 1) != 0) << endl;
    return 0;
}

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

int main(){
    cin>>a>>b>>k;
    int cnt = 0;
    int i;
    for(i=max(a,b);i>=1;i--){
        if(a%i==0 && b%i==0){
            cnt++;
            if(cnt==k) break ;
        }
    }
    cout<<i;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int n, A[2000];

int solve(int i, int m){
  if(m==0) return 1;
  if(i>=n) return 0;
  int res = solve(i+1, m) || solve(i+1, m-A[i]);
  return res;
}

int main(){
  int q, M, i;

  scanf("%d", &n);
  for(i=0; i<n; i++) scanf("%d", &A[i]);
  scanf("%d", &q);
  for(i=0; i<q; i++) {
    scanf("%d", &M);
    if(solve(0, M)) printf("yes\n");
    else printf("no\n");
  }

  return 0;
}

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

int main() {
  int N,N1,N2,N3,N4;
  cin >> N;
  N1 = N/1000;
  N2 = (N-N1*1000)/100;
  N3 = (N-N1*1000-N2*100)/10;
  N4 = N%10;
  if(N1 == N2 && N2 == N3 || N2 == N3 && N3 == N4)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define cerr                                                                   \
  if (false)                                                                   \
  cerr

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

bool L[100100];

void solve(long long N, long long K, vector<long long> a) {
  ll all = 0;
  ll center = 0;
  ll ans = 0;

  REP(i, N) {
    if (i < K) {
      center += a[i];
    } else {
      all += max(a[i], 0LL);
    }
  }

  ans = max(0LL, max(center, 0LL) + all);

  FOR(i, K, N) {
    all -= max(a[i], 0LL);
    center += a[i];

    center -= a[i - K];
    all += max(a[i - K], 0LL);

    ans = max(ans, max(center, 0LL) + all);
  }

  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long N;
  long long K;
  cin >> N;
  vector<long long> a(N - 1 + 1);
  cin >> K;
  for (int i = 0; i <= N - 1; i++) {
    cin >> a[i];
  }
  solve(N, K, a);
  return 0;
}


Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    private int N;
    private int[,]A;
    private void Scan()
    {
        N=int.Parse(Console.ReadLine());
        A=new int[N,N];
        for(int i=0;i<N;i++)
        {
            var l=Console.ReadLine().Split(' ');
            for(int j=0;j<N;j++)
            {
                A[i,j]=int.Parse(l[j]);
            }
        }
    }
    
    
    
    public void Solve()
    {
        Scan();
        var not=new bool[N,N];
        for(int k=0;k<N;k++)
        {
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<N;j++)
                {
                    if(i==j||j==k||k==i)continue;
                    
                    if(A[i,j]==A[i,k]+A[k,j])
                    {
                        not[i,j]=true;
                    }
                    if(A[i,j]>A[i,k]+A[k,j])
                    {
                        Console.WriteLine(-1);
                        return;
                    }
                }
            }
        }
        long ans=0;
        for(int i=0;i<N-1;i++)
        {
            for(int j=i+1;j<N;j++)
            {
                if(not[i,j])continue;
                ans+=A[i,j];
            }
        }
        Console.WriteLine(ans);
    } 
    
    static void Main()
    {
        new Program().Solve();
    }
}

Measured memory_bytes: 19032
#include <iostream>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>


using namespace std;
typedef long long ll;
typedef long double ld;
const int MX=3e5+9;
const long double eps=-0.00000001;
const ll mod = 1e9+7;



int main()
{
    ll x;
    cin>>x;

    ll ans=1e18;

    ll st=-1,en=1e15;
    ll mid;

    while ( st<=en )
    {
        mid = st+(en-st)/2;
        ll temp = 5*mid+6*mid;
        if ( temp>=x ) { ans=min(2*mid,ans); en=mid-1; }
        else if ( temp+6>=x ) { ans=min(ans,2*mid+1); en=mid-1; }
        else{ st=mid+1; }
    }

    cout<<ans;



    return 0;
}


Measured memory_bytes: 256
from bisect import bisect_left, bisect_right

n = int(input())
a = sorted(map(int, input().split()))
b = map(int, input().split())
c = sorted(map(int, input().split()))

ans = 0
for bb in b:
    ans += bisect_left(a, bb) * (n - bisect_right(c, bb))

print(ans)


Measured memory_bytes: 25920
<?php
function getArrayFromStdin() {
	$line = trim(fgets(STDIN));
	$line = str_replace(array("\r\n","\r","\n"), '', $line);
	$line = explode(" ", $line);
	return $line;
}

$arr = getArrayFromStdin();

$sum = 0;
for ($i = 1; $i <= $arr[0]; $i++) {
  $str = (string)$i;
  $stringArr = str_split($str);
  $sumOfEachDigit = 0;
  foreach($stringArr as $s) {
    $sumOfEachDigit += (int)$s;
  }
  if ($sumOfEachDigit >= $arr[1] && $sumOfEachDigit <= $arr[2]) {
    $sum += $i;
  }
}

echo $sum;

Measured memory_bytes: 4604
#include <iostream>
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int,int>;
using ll = long long;


int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> before(n);
    vector<ll> after(n);
    rep(i,n) cin>>a[i];

    rep(i,n){
        if(0<=i-a[i]){
            before[i-a[i]]++;
        }
        if(i+a[i]<=n-1){
            after[i+a[i]]++;
        }
    }
    ll ans=0;
    rep(i,n){
        ans+=before[i]*after[i];
    }
    cout << ans <<endl;
}

Measured memory_bytes: 8024
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();

        long n = sc.nextLong();

        List<Long> list1 = new ArrayList<>();
        List<Long> list2 = new ArrayList<>();

        for (long i = 1; i < (long)Math.sqrt(n)+1; i++) {
            if (n % i == 0) {
                list1.add(i);
                list2.add(n / i);
            }
        }

        long ans = Long.MAX_VALUE;
        for (int i = 0; i < list1.size(); i++) {
            long a = list1.get(i);
            long b = list2.get(i);
            ans = Math.min(ans, a + b - 2);
        }

        System.out.println(ans);
    }

    static class MyScanner {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 15);
        StringTokenizer tokenizer;

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Measured memory_bytes: 21844
h, w = map(int, input().split())
a = [input() for i in range(h)]
vdel = []
sdel = []

for i in range(h):
    if a[i].count('.') == w:
        sdel.append(i)

for i in range(w):
    cnt = 0
    for j in range(h):
        if a[j][i] == '.':
            cnt += 1
    if cnt == h:
        vdel.append(i)
i = 0
lens = len(sdel)-1
h -= lens+1
while i <= lens:
    del a[sdel[lens]]
    lens -= 1

for i in range(h):
    tmp = ''
    for j in range(w):
        if j not in vdel:
            tmp += a[i][j]
    print(tmp)

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


int main(){
	ll a,b,c,mn;
	scanf("%lld%lld%lld",&a,&b,&c);
	
	if(c%2==0) mn=0;
	else mn=a*b;
	
	if(b%2==0) mn=0;
	else mn=min(mn,a*c);
	
	if(a%2==0) mn=0;
	else mn=min(mn,b*c);
	printf("%lld",mn);
	return 0;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  int n;
  cin >> n;
  int b[100000];

  int s = 0;
  for (int i = 0; i < n - 1; i++){
    cin >> b[i];
  }


  s += b[0] + b[n - 2];
  for (int i = 1; i < n - 1; i++){
    s += min(b[i], b[i - 1]);
  }


  cout << s << endl;

  return 0;
}


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

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, x) for(ll i = 0; i < x; i++)
#define rep2(i, x) for(ll i = 1; i <= x; i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ld pi = 3.141592653589793238;

ll test[12345678];
signed main() {
	string s, t;
	ll n, m, k, q, a = 0, b = 0, c = 0, d, x, y, ans = 1;
	cin >> n >> k;
	rep(i, n) {
		cin >> test[i];
	}
	ll ok = 0, ng = mod, mid = (ok + ng) / 2;
	while (ng - ok > 1) {
		ll cnt = 0;
		rep(i, n) {
			if (mid != 0) {
				cnt += (test[i] + mid - 1) / mid; cnt--;
			}
		}
		if (cnt > k) { ok = mid; }
		else { ng = mid; }
		mid = (ok + ng) / 2;
	}
	cout << ng << endl;
	return 0;
}

Measured memory_bytes: 5164
#include<bits/stdc++.h>
using namespace std;
const long long M =1e6+10,MOD=1000000000;
typedef long long ll;
ll a[M],b[M];
ll tot=0;
map<ll,ll>mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;
    cin>>n>>m;
    cout<<min((n%m),abs((n%m)-m))<<endl;

 
    return 0;
  }

Measured memory_bytes: 256