akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n; cin >> n;
    vector<pair<ll,ll>> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(ALL(a),greater<pair<ll,ll>>());

    vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
    for(int i=0;i<n;i++){
        for(int j=0;i+j<n;j++){
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]+a[i+j].first * (a[i+j].second - i));
            dp[i][j+1] = max(dp[i][j+1],dp[i][j]+a[i+j].first * (n-1-j - a[i+j].second));
        }
    }

    ll ans = 0;
    for(int i=0;i<=n;i++) ans = max(ans,dp[i][n-i]);
    cout << ans << endl;

    return 0;
}

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

int n;
int p[20];

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



Measured memory_bytes: 256
import java.util.*;
public class Main {
   private static int p[][];
   private static int dp[][];
  public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();

        p = new int[n][3];
        dp = new int[n][3];

        for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
          p[i][j] = sc.nextInt();
        }}

//3
//10 40 70
//20 50 80
//30 60 90
    	dp[0][0]=p[0][0];
    	dp[0][1]=p[0][1];
    	dp[0][2]=p[0][2];

    
		for (int i=1; i < n; i++) {
		for (int j=0; j < 3; j++) {
		for (int k=0; k < 3; k++) {
			if (j==k) continue;
			dp[i][k]=chmax(dp[i-1][j]+p[i][k],dp[i][k]);
		}}}
		System.out.println(chmax(chmax(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
	}

	private static int chmax(int i, int j) {
		return Math.max(i, j);
	}
}







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

int main() {
  int a, b, mean_i;
  double mean_d;
  cin >> a >> b;
  mean_i = (a + b) / 2;
  mean_d = ((double) a + (double) b) / 2;
  if (mean_d > (double) mean_i) {
  	mean_i += 1;
  }
  cout << mean_i << endl;
}

Measured memory_bytes: 256
odd =input()
even=input()
a=[]
if len(odd) == len(even):
    for i in range(len(odd)):
        a.append(odd[i])
        a.append(even[i])
else:
    for i in range(len(odd)):
        a.append(odd[i])
        if i != len(odd)-1:
            a.append(even[i])
print("".join(a))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
bool is_prime(ll N) {
    if (N == 1) return false;
    for (ll i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}
int main() {
  vector<int> likenum;
  for (int i = 1; i <= 100000; i+=2) {
    if (is_prime(i) && is_prime((i+1)/2)) {
      likenum.push_back(i);
    }
  }

  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l,r;
    cin >> l >> r;
    auto itr = lower_bound(likenum.begin(),likenum.end(),l);
    auto itr2 = upper_bound(likenum.begin(),likenum.end(),r);
    cout << itr2 - itr << endl;
  }
  return 0;
}

Measured memory_bytes: 640
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] count = new int[N+1];
		for( int i=0; i<K; i++ ){
			int D = sc.nextInt();
			for( int k=0; k<D; k++ ){
				int a = sc.nextInt();
				count[a]++;
			}
		}
		int ans = 0;
		for( int i=1; i<=N; i++ ){
			if( count[i]==0 ){
				ans++;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 46208
# じょえチャンネル
# 高評価・チャンネル登録宜しくお願いします！
# https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ

import sys
from fractions import gcd
from itertools import groupby as gb
from itertools import permutations as perm
from itertools import combinations as comb
from collections import Counter as C
from collections import defaultdict as dd
sys.setrecursionlimit(10**5)
def y(f):
    if f:
        print('Yes')
    else:
        print('No')
def Y(f):
    if f:
        print('YES')
    else:
        print('NO')
def Z(f):
    if f:
        print('Yay!')
    else:
        print(':(')
def ispow(n):
    if int(n**.5)**2==n:
        return True
    return False

n = int(input())
a = list(map(int,input().split()))

res = 10 ** 100
for i in range(-100, 200):
    tmp = 0
    for j in a:
        tmp += (i - j) ** 2
    res = min(res, tmp)
print(res)


Measured memory_bytes: 5076
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam))
  #-swank (set-dispatch-macro-character #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil (values) t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read))
         (k (read))
         (cumuls+ (make-array (+ 1 n) :element-type 'fixnum :initial-element 0))
         (cumuls (make-array (+ 1 n) :element-type 'fixnum :initial-element 0)))
    (declare (uint32 n k))
    (dotimes (i n)
      (let ((a (read-fixnum)))
        (setf (aref cumuls+ (+ i 1)) (+ (max 0 a) (aref cumuls+ i))
              (aref cumuls (+ i 1)) (+ a (aref cumuls i)))))
    (println
      (loop for cept from 0 to (- n k)
            maximize (+ (aref cumuls+ cept)
                        (- (aref cumuls+ n)
                           (aref cumuls+ (+ cept k)))
                        (max 0 (- (aref cumuls (+ cept k))
                                  (aref cumuls cept))))
            of-type fixnum))))

#-swank(main)


Measured memory_bytes: 12776
// ABC065 B - Trained?
#include <stdio.h>

int main(void) {
    int N;  // 10^5
    scanf("%d", &N);
    int a[N + 1];
    int flag[100001] = { 0 };
    for (int i = 1; i <= N; i++) {
        scanf("%d", &a[i]);
    }
    int i = 1;
    int count = 0;
    while(1) {
        count++;
        int onButton = a[i];
        if (onButton == 2) {
            printf("%d\n", count);
            return 0;
        }
        if (flag[onButton] == 1) {
            printf("%d\n", -1);
            return 0;
        } else {
            flag[onButton] = 1;
        }
        i = onButton;
    }
}

Measured memory_bytes: 896
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
    char N[5];
    scanf("%s",&N);
    if(N[0]=='7'||N[1]=='7'||N[2]=='7')
    {
        printf("Yes\n");
    } else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 2084
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev


def main():
	N = int(input())
	abc = []
	for i in range(N):
		a,b,c = map(int, input().split(" "))
		abc.append((a,b,c))
		
	DP = [[0 for _ in range(3)] for _ in range(N)]
	
	for i, val in enumerate(abc):
		a, b, c = val
		if i == 0:
			DP[i][0] = a
			DP[i][1] = b
			DP[i][2] = c
			continue
		DP[i][0] = max(DP[i-1][1] + a, DP[i-1][2] + a)
		DP[i][1] = max(DP[i-1][0] + b, DP[i-1][2] + b)
		DP[i][2] = max(DP[i-1][0] + c, DP[i-1][1] + c)
		
	print(max(DP[N-1][0], DP[N-1][1], DP[N-1][2]))
	
	
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 42228
#include <stdio.h>
#include <map>
#include <algorithm>
#define N 100010
typedef long long ll;
using namespace std;
int n,c,a[N],b[N];ll ans[N];
struct data {
	int f,cnt;
};
map<int,data> m;
char buf[30];
inline void outll(ll x) {
	if(!x) {
		puts("0");
		return;
	}
	int i=0;
	for(;x;x/=10) buf[i++]='0'+x%10;
	while(i--) putchar(buf[i]);
	puts("");
}
int main() {
	scanf("%d",&n);
	for(int i=0;i<n;++i) {
		scanf("%d",a+i);
		b[i]=a[i];
		data &d=m[a[i]];
		if(!d.cnt) d.f=i;
		++d.cnt;
	}
	b[n]=0;sort(b,b+n+1);
	c=unique(b,b+n+1)-b;
	for(int i=c-1;i;--i) {
		data &d=m[b[i]],&e=m[b[i-1]];
		ans[d.f]+=d.cnt*ll(b[i]-b[i-1]);
		e.cnt+=d.cnt;
		if(d.f<e.f) e.f=d.f;
	}
	for(int i=0;i<n;++i) outll(ans[i]);
	return 0;
}

Measured memory_bytes: 8832
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long ;
int main(){
    int n;
    cin >> n;
    if(n>= 400 && n<=599) cout << 8 << endl;
    else if(n>= 600 && n<=799) cout << 7 << endl;
    else if(n>= 800 && n<=999) cout << 6 << endl;
    else if(n>= 1000 && n<=1199) cout << 5 << endl;
    else if(n>= 1200 && n<=1399) cout << 4 << endl;
    else if(n>= 1400 && n<=1599) cout << 3 << endl;
    else if(n>= 1600 && n<=1799) cout << 2 << endl;
    else cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 3608
package main

import (
	"fmt"
)

func main() {
	var a, b, c, x int
	fmt.Scan(&a, &b, &c, &x)

	var count int
	for i := a; i >= 0; i-- {
		for j := b; j >= 0; j-- {
			for k := c; k >= 0; k-- {
				if 500*i+100*j+50*k == x {
					count++
				}
			}
		}
	}
	fmt.Println(count)
}


Measured memory_bytes: 512
#include <stdio.h>
#define swap(type, x, y) do{ type t = x; x = y; y = t; }while(0)

int main(){
  int n;  scanf("%d", &n);
  int v[55];
  for(int i=1; i<=n; i++)
    scanf("%d", v+i);

  for(int i=1; i<n; i++)
    for(int j=i+1; j<=n; j++){
      if(v[i] > v[j])
	swap(int, v[i], v[j]);
    }

  double ans = (double)v[1];
  for(int i=2; i<=n; i++)
    ans = (ans + (double)v[i]) / 2.0;

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


Measured memory_bytes: 1748
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
int n;
cin>>n;
string s[n];
cin>>s[0];
FOR(i,1,n){
cin>>s[i];
if(s[i-1][s[i-1].size()-1]!=s[i][0]){
cout<<"No"<<endl;
return 0;
}
REP(j,i){
if(s[i]==s[j]){
cout<<"No"<<endl;
return 0;
}
}
}
cout<<"Yes"<<endl;

    return 0;
}

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

int main() {
  string s;
   cin>>s;
  if(s=="SUN"){
    cout<<7<<endl;
  }
  else if(s=="SAT"){
    cout<<1<<endl;
  }
  else if(s=="FRI"){
    cout<<2<<endl;
  }
  else if(s=="THU"){
    cout<<3<<endl;
  }
  else if(s=="WED"){
    cout<<4<<endl;
  }
  else if(s=="TUE"){
    cout<<5<<endl;
  }
  else if(s=="MON"){
    cout<<6<<endl;
  }
  
}

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

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define lli long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

#define forn(i, n)  for(int i=0;i<n;++i)
#define rforn(i,start) for(int i = start; i >= 0;--i)
#define forsn(i,start,end) for(int i=start;i<end;++i)
#define rforsn(i,start,end) for(int i=start;i>=end;--i)
#define debug(x) cout<<#x<<" = "<<x<<"\n";
const int CONST = 1e9 + 7;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
	//    freopen("input.txt", "r", stdin);
	//  freopen("output.txt","w",stdout);
	#endif

    int n;
    cin>>n;
    int ht[n];
    forn(i, n){
        cin>>ht[i];
    }
    int dp[n];
    dp[n-1]=0;

    rforsn(i, n-2, 0){
        dp[i]=INT_MAX;
        for(int j=1; j<=2 && (i+j)<n; ++j){
            dp[i] = min(dp[i+j]+ abs(ht[i+j]-ht[i]), dp[i]);
        }
    }
    cout<<dp[0];
	return 0;
}


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

int main(void)
{
	double a,b,c,d,e,f,x,y,iptr;

	while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF) {
		y=(a*f-c*d)/(a*e-b*d);
		x=(c-b*y)/a;
		x=(int)(x*10000);
		x+=modf(x,&iptr)>=0.5?1:0;
		y=(int)(y*10000);
		y+=modf(y,&iptr)>=0.5?1:0;
		x/=10000;
		y/=10000;
		printf("%.3f %.3f\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 660
#include <bits/stdc++.h>
#define L(x) ((x) & -(x))
const int N = 100005;
std::vector<int> e[100005];
int n, m, s[N], a;
void U(int x, int u) {
  while (x <= n)
    s[x] += u, x += L(x);
}
int Q(int x) {
  int r = 0;
  while (x)
    r += s[x], x -= L(x);
  return r;
}
int main() {
  scanf("%d%d", &m, &n);
  for (int i = 1, l, r; i <= m; i++)
    scanf("%d%d", &l, &r), e[r - l + 1].push_back(l);
  for (int d = 1; d <= n; d++) {
    a = m;
    for (int i = d; i <= n; i += d)
      a += Q(i);
    for (int u : e[d])
      U(u, 1), U(u + d, -1), m--;
    printf("%d\n", a);
  }
  return 0;
}

Measured memory_bytes: 6912
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <cfloat>
#define zero(x) (((x)>0?(x):-(x))<eps)

#define pause cout << " press ansy key to continue...",  cin >> chh
#define file_r(x) freopen(x,  "r",  stdin)
#define file_w(x) freopen(x,  "w",  stdout)
#define lowbit(x) ((x) & (-x))
#define repit(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repe(i, u) for (int i = head[u]; i != -1; i = nxt[i])
#define repd(i, n) for (int i = (n - 1); i >= 0; i--)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
#define FORD(i, n, m) for (int i = (n); i >= (m); i--)
#define pb push_back
#define X first
#define Y second
#define ins insert
#define rb rbegin
#define be begin
#define er erase
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define SZ(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define sqr(r) ((r) * (r))
#define dis(x1, y1, x2, y2) (((x1) - (x2)) * ((x1) - (x2)) + ((y1) - (y2)) * ((y1) - (y2)))
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

#define sc(x) cout << #x" = " << x << endl, system("pause")
#define sc2(x, y) cout << #x" = " << x << " " << #y" = " << y << endl, system("pause")
#define sc3(x, y, z) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << endl, system("pause")
#define sc4(x, y, z, w) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << " " << #w" = " << w << endl, system("pause")

#define in(n) scanf("%d", &n)
#define in2(n, m) scanf("%d %d", &n, &m)
#define in3(x, y, z) scanf("%d %d %d", &x, &y, &z)

using namespace std;
int chh;

typedef vector<int> vi;
typedef set<int> si;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<int, pii> pi3;
typedef vector< pair<int, int> > vpii;
typedef long long LL;

const int N = 20005;

int n;
int p[N], a[N], b[N];
int L[N], R[N];

int main() {
    int t, pre, id;
    while (~in(n)) {
        FOR (i, 1, n) in(p[i]);
        a[1] = 1;
        FOR (i, 2, n) a[i] = a[i - 1] + n;
        t = 1;
        FORD (i, n, 1) {
            L[i] = t, R[i] = L[i] + n - 1;
            t += n;
        }
        pre = 0;
        FOR (i, 1, n) {
            id = p[i];
            if (L[id] + a[id] > pre) b[id] = L[id];
            else {
                b[id] = pre + 1 - a[id];
            }
            pre = a[id] + b[id];
        }
        FOR (i, 1, n - 1) printf("%d ", a[i]);
        printf("%d\n", a[n]);
        FOR (i, 1, n - 1) printf("%d ", b[i]);
        printf("%d\n", b[n]);
    }
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;
const ll mod = 1000000007;

void end(){
    cout << 0 << endl;
}

ll RepeatSquaring(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P%2==0){
        ll t = RepeatSquaring(N, P/2, M);
        return t*t % M;
    }
    return N * RepeatSquaring(N, P-1, M);
}

int main(){
    int A[100010] = {0};
    ll n, a;
    cin >> n;
    if(n%2 == 0){
        for (int i = 0; i < n; i++) {
            cin >> a;
            if(a%2 == 0){
                end();
                return 0;
            }
            A[(a-1)/2]++;
        }
        for (int i = 0; i < n/2; i++) {
            if(A[i] != 2){
                end();
                return 0;
            }
        }
    }
    else{
        for (int i = 0; i < n; i++) {
            cin >> a;
            if(a%2 != 0){
                end();
                return 0;
            }
            A[a/2]++;
        }
        for (int i = 0; i < (n+1)/2; i++) {
            if(i==0){
                if(A[i] != 1){
                    end();
                    return 0;
                }
            }
            else{
                if(A[i] != 2){
                    end();
                    return 0;
                }
            }
        }
    }
    cout << RepeatSquaring(2, n/2, mod) << endl;
    return 0;
}


Measured memory_bytes: 640
N = int(input())
robot = [input().split() for i in range(N)]

le = [[int(i[0])-int(i[1]), int(i[0])+int(i[1])] for i in robot]
le.sort(key = lambda x:x[1])

ans = 0
floor = -10**9-1
for i in range(N):
    if floor <= le[i][0]:
        ans += 1
        floor = le[i][1]

print(ans)

Measured memory_bytes: 52136
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, pair<string, int>> SP;
#define mp(a, b) make_pair(a, b)

bool comp(SP lhs, SP rhs) {
  if (lhs.second.first != rhs.second.first) {
    // return lhs.second.first.compare(rhs.second.first);
    return lhs.second.first <= rhs.second.first;
  } else {
    //    return lhs.second.first.compare(rhs.second.first);
    return lhs.second.second > rhs.second.second;
  }
}

int main(int argc, char const *argv[]) {
  int n, l;

  cin >> n;
  cin >> l;

  int value;
  int total = 0;
  int minval = 999999999;
  int val;
  for (int i = 0; i < n; i++) {
    value = l + i;
    total += value;
    if(abs(value) < minval){
      minval = abs(value);
      val = value;
    }
  }

  cout << total - val;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fio(s) freopen(s".inp","r",stdin)
#define foo(s) freopen(s".out","w",stdout)
#define task "test"
using namespace std;
typedef long long LL;
const LL N=100009,OO=1e9+7;
LL n,m,ans,d[N];
vector<LL> par[N];
LL cal(LL v){
    if(d[v]!=-1) return d[v];
    d[v]=0;
    for(auto u:par[v]) d[v]=max(d[v],cal(u)+1);
    ans=max(ans,d[v]);
    return d[v];
}
int main(){
    //fio(task); foo(task);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    LL u,v;
    For(i,1,m){
        cin>>u>>v; par[v].push_back(u);
    }
    memset(d,255,sizeof(d));
    For(i,1,n) if(d[i]==-1) cal(i);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
#define int     long long
#define F       first
#define S       second
#define _READ   freopen("input.txt","r", stdin);
#define _FAST   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
void solve()
{
    int n;
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
            sum+=i;
    }
    cout<<sum<<" ";
}
int32_t main()
{
    clock_t tStart = clock();
    #ifndef ONLINE_JUDGE
    //_READ
    #endif
    
    int t;
    t=1;
    while(t--)
        solve();
    
    #ifndef ONLINE_JUDGE
    cout<<fixed<<setprecision(5)<<"\nTime taken: "<<(double)(clock() - tStart)/CLOCKS_PER_SEC;
    #endif
    
    return 0;
}
/*
===FOR N-Dimensional Vector===
https://codeforces.com/blog/entry/76149
g++ -std=c++17 -Wshadow -Wall -g -fsanitize=address -fsanitize=undefined a.cpp -o a -D_GLIBCXX_DEBUG
*/

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



Measured memory_bytes: 2148
#include <bits/stdc++.h>
#if 1
#define int long long
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define stoi stoll
#else
#define MAX INT_MAX
#define MIN INT_MIN
#endif
#define INF MAX/2
#define ALL(obj) (obj).begin(), (obj).end()
#define fi first
#define se second
const int NIL = -1;
const int MOD = 1000000007;
#define REP(i,n) for (int (i)=0; (i) < (n); ++i)
#define FOR(i,a,b) for (int (i)=(a); (i) < (b); ++i)
using namespace std;

int pow(int x, int n) {int res=1; while(n){if(n&1)res*=x;x*=x;n>>=1;} return res;}
int get_gcd(int a, int b) {while(1){if (a < b) swap(a, b); if (b == 0) return a; a %= b;}}
int get_lcm(int a, int b) {return a * b / get_gcd(a, b);}
bool chmin(int &a, int b) {if(a>b){a=b; return true;} else return false;}
bool chmax(int &a, int b) {if(a<b){a=b; return true;} else return false;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//-------------------------テンプレここまで-------------------------//

signed main () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N;
  cin >> N;
  vector<double> p(N);
  REP(i,N) cin >> p[i];

  //dp[i[j]] ... 最初のi枚中、表がj枚である確率（1-index)
  static double dp[3000][3000];
  dp[0][0] = 1;

  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= i; j++) {
      //i枚目が表だった場合
      if (j-1>=0) dp[i][j] += dp[i-1][j-1] * p[i-1];
      //i枚目が裏だった場合
      dp[i][j] += dp[i-1][j] * (1.0 - p[i-1]);
    }
  }

  //足し上げるときの情報落ちを防ぐためのpriotry_queue
  priority_queue<double,vector<double>,greater<double>> pq;
  for (int j = (N+1)/2; j <=N; j++) {
    pq.push(dp[N][j]);
  }
  while (pq.size() > 1) {
    double x = pq.top(); pq.pop();
    double y = pq.top(); pq.pop();
    pq.push(x+y);
  }

  cout << setprecision(16) << pq.top() << endl;

  return 0;
}


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

long long dfs(vector<vector<long long>> &dp, const vector<long long> &a, int l, int r, bool flag, const long long init)
{
    if (dp[l][r] == init)
    {
        long long sign;
        if (flag)
        {
            sign = 1;
        }
        else
        {
            sign = -1;
        }

        if (l == r)
        {
            dp[l][r] = sign * a[l];
        }
        else
        {
            long long left = sign * a[l] + dfs(dp, a, l + 1, r, flag ^ 0x1, init);
            long long right = sign * a[r] + dfs(dp, a, l, r - 1, flag ^ 0x1, init);
            if (flag)
            {
                dp[l][r] = max(left, right);
            }
            else
            {
                dp[l][r] = min(left, right);
            }
        }
    }
    return dp[l][r];
}

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

    vector<long long> a(N);
    for (long long &elem : a)
    {
        cin >> elem;
    }

    const long long init = LONG_LONG_MAX;
    vector<vector<long long>> dp(N, vector<long long>(N, init));
    int l = 0;
    int r = N - 1;
    cout << dfs(dp, a, l, r, true, init) << endl;
}


Measured memory_bytes: 71040
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int d;
	cin >>d;
	Vi ans(d,0);
	Vi c(26,0);
	ll sum=0LL;
	rep(i,26){
		cin>>c[i];
		sum+=c[i];
	}
	VVi s(d,Vi(26,0));
	rep(i,d){
		rep(j,26){
			cin>>s[i][j];
		}
	}
	int up=1;
	int val=-INF;
	int now=0;
	ll pen=0LL;
	Vi last(26,0);
	rep(i,d){
		val=-INF;
		rep(j,26){
			now=0;
			now=s[i][j]-pen-sum-c[j]+(i+1-last[j]);
			
			if(chmax(val,now)){
				up=j;
			}
		}
		ans[i]=up;
		pen += sum-(i+1-last[up])*c[up];
		last[ans[i]] = i + 1;
	}
	rep(i,d){
		cout<<ans[i]+1<<endl;
	}
	
}

Measured memory_bytes: 3680
import Control.Monad
import Data.Char

main = do
    s <- getLine
    k <- read <$> getLine
    putStrLn $ show $ digitToInt $ solve s k

solve :: String -> Int -> Char
solve (h:t) k | k == 1    = h
              | h /= '1'  = h
              | otherwise = solve t (k - 1)

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define trav(x, a) for (auto& x: a)

const int MX  = 2e5+5;
const int MOD = 1e9+7;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

ll dp[105][MX],arr[MX];

int main() {

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

    int N,K; cin >> N >> K;

    FOR(i,1,N+1) cin >> arr[i];

    dp[0][0] = 1;
    FOR(i,1,N+1) {
        FOR(j,1,K+1) dp[i-1][j] = (dp[i-1][j]+dp[i-1][j-1])%MOD;
        F0R(j,K+1) dp[i][j] = (dp[i][j]+((dp[i-1][j]-(j > arr[i] ? dp[i-1][j-arr[i]-1] : 0)+MOD)%MOD))%MOD;
    }

    cout << dp[N][K] << "\n";

}


Measured memory_bytes: 158464
#ifndef ___CLASS_MODINT
#define ___CLASS_MODINT

#include <cstdint>

template<std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::uint64_t n_) : n(n_ % mod) {};
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	std::uint32_t get() const { return n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint binpow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
	modint inv() { return (*this).binpow(mod - 2); }
};

#endif // ___CLASS_MODINT

#include <vector>
#include <iostream>
#include <functional>
using namespace std;
using modulo = modint<1000000007>;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<vector<int> > G(N);
	for (int i = 0; i < N - 1; ++i) {
		int A, B;
		cin >> A >> B; --A, --B;
		G[A].push_back(B);
		G[B].push_back(A);
	}
	function<vector<modulo>(int, int)> calc = [&](int pos, int pre) {
		vector<modulo> ans(2, modulo(1));
		for (int i : G[pos]) {
			if (i != pre) {
				vector<modulo> sub = calc(i, pos);
				ans[0] *= sub[0] + sub[1];
				ans[1] *= sub[0];
			}
		}
		return ans;
	};
	vector<modulo> ret = calc(0, -1);
	cout << (ret[0] + ret[1]).get() << '\n';
	return 0;
}

Measured memory_bytes: 19584
N = int(input())
A = input()
B = input()
C = input()

ans = 0
for i in range(N):
    if A[i] == B[i] and B[i] == C[i]:
        ans += 0
    elif A[i] == B[i] and B[i] != C[i] \
        or B[i] == C[i] and C[i] != A[i] \
        or C[i] == A[i] and A[i] != B[i]:
        ans += 1
    else:
        ans += 2

print(ans)


Measured memory_bytes: 3064
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back
using namespace std; 
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef pair<long,long> pll;
typedef long long ll;



int main(){
	int n,m;
	cin >> n >> m;
	int V[n+1],W[n+1];
	int T[n+1][m+1];
	for(int i = 1;i <= n;i++){
		cin >> V[i] >> W[i];
	}
	for(int i = 0;i <= m;i++){
		T[0][i] = 0;
	}
	for(int i = 0;i <= n;i++){
		T[i][0] = 0;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(W[i] <= j){
				if(V[i] + T[i-1][j-W[i]] > T[i-1][j]){
					T[i][j] = V[i] + T[i-1][j-W[i]];
				}else{
					T[i][j] = T[i-1][j];
				}
			}else{
				T[i][j] = T[i-1][j];
			}
		}
	}
	int max = -1;
	for(int i = 0;i <= n;i++){
		for(int j = 0;j <= m;j++){
			if(T[i][j] > max) max = T[i][j];
		}
	}
	P(max);
	return 0;
}

Measured memory_bytes: 5104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = 1e9 + 7;

void solve() {
	int h, w; cin >> h >> w;
	vector<vector<ll>> dp(h + 1, vector<ll>(w + 1, 0));
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < w; ++j) {
			char c; cin >> c;
			if (c == '#') {
				dp[i + 1][j + 1] = -1;
			}
		}
	}
	dp[0][1] = 1;
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			if (dp[i][j] < 0) {
				dp[i][j] = 0; continue;
			}
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
		}
	}
	cout << dp[h][w];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	// #ifndef ONLINE_JUDGE
	//     freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	// #endif
	solve();
	return 0;
}


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

using namespace std;

typedef long long ll;

int main(void){
  int n;
  ll c;
  cin >> n >> c;
  vector<ll> x=vector<ll>(n, 0), v=vector<ll>(n, 0);
  for(int i = 0; i < n; ++i)
    cin >> x[i] >> v[i];
  vector<ll> cal_1, cal_1_max;
  ll max_cal = 0;
  cal_1.push_back(v[0] - x[0]);
  cal_1_max.push_back(cal_1[0]);
  max_cal = max(max_cal, cal_1[0]);
  //cout << cal_1[0] << endl;
  for(int i = 1; i < n; ++i){
    cal_1.push_back(v[i] + cal_1[i-1] - x[i] + x[i-1]);
    cal_1_max.push_back(max(cal_1[i], cal_1_max[i-1]));
    max_cal = max(max_cal, cal_1[i]);
    //cout << cal_1[i] << endl;
  }

  vector<ll> cal_2=vector<ll>(n, 0), cal_2_max=vector<ll>(n, 0);
  cal_2[n-1] = v[n-1] - c + x[n-1];
  cal_2_max[n-1] = cal_2[n-1];
  max_cal = max(max_cal, cal_2[n-1]);
  //cout << cal_2[n-1] << endl;
  for(int i = n-2; i >= 0; --i){
    cal_2[i] = v[i] + cal_2[i+1] + x[i] - x[i+1];
    cal_2_max[i] = max(cal_2[i], cal_2_max[i+1]);
    max_cal = max(max_cal, cal_2[i]);
    //cout << cal_2[i] << endl;
  }

  for(int i = 0; i < n-1; ++i){
    max_cal = max(max_cal, cal_1[i] - x[i] + cal_2_max[i+1]);
  }

  for(int i = n-1; i > 0; --i){
    max_cal = max(max_cal, cal_2[i] - c + x[i] + cal_1_max[i-1]);
  }
  cout << max_cal << endl;
  return 0;
}


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

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
#define guard(x) if( not ( x ) ) continue;
typedef int64_t Int;
typedef std::vector<Int> LI;
const double pi = 3.14159265358979323846264338;
const Int mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(Int& x) { if( scanf("%" PRId64, &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(Int &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      std::string ss; scan(ss);
      Int n = ss.size();
      for(Int i = 0; i < n - 8; ++i) {
         putchar(ss[i]);
      }
      putchar('\n');
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}




Measured memory_bytes: 256
n = int(input())
ps = list(map(int, input().split()))

cnt = 0
for i in range(1, n-1):
    i_and_neighbours = [ps[i-1], ps[i], ps[i+1]]
    if ps[i] != max(i_and_neighbours) and ps[i] != min(i_and_neighbours):
        cnt += 1
        
print(cnt)

Measured memory_bytes: 3060
n=int(input())
p=list(map(int, input().split()))
count=0
for i in range(1,n-1):
    if (p[i-1]<p[i] and p[i]<p[i+1]) or (p[i-1]>p[i] and p[i]>p[i+1]):
        count+=1
print(count)

Measured memory_bytes: 3060
# A - Five Antennas
# https://atcoder.jp/contests/abc123/tasks/abc123_a
NUM_ANTENNAS = 5
antennas = list()
for _ in range(NUM_ANTENNAS):
    antennas.append(int(raw_input()))
k = int(raw_input())
print 'Yay!' if (antennas[-1]-antennas[0]) <= k else ':('


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

int main() {
  ll N = 3;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
  }
  sort(A.begin(), A.end()); //小さい順
  cout << A[0] + A[1];
}

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

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

  if((a+b)%2 == 0) cout << (a+b)/2 << endl;
  else cout << "IMPOSSIBLE" << endl;

  return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200200;
int N;
int a[maxn];
int b[maxn];
int check(int x){
	for (int i = 1; i<=2*N-1;i++) b[i] = (a[i]>=x?1:0);
	for (int i = 1 ; i <=N-1;i++){
		if (b[N+i]==b[N+i-1])return b[N+i];
		if (b[N-i]==b[N-i+1])return b[N-i];
	}
	return b[1];
}
int main(){
	scanf("%d",&N);
	for (int i = 1 ; i <= 2*N-1 ; i++) scanf("%d",&a[i]);
	int L=1,R=2*N;
	while (L<R){
		int mid = L+(R-L)/2;
		if (check(mid))L=mid+1;
		else R=mid;
	}
	printf("%d\n",L-1);

	return 0;
}

Measured memory_bytes: 1920
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

typedef long long ll;

int main(){
  ll n,W;
  cin>>n>>W;
  vector<ll> wl = vector<ll>(n);
  vector<ll> vl = vector<ll>(n);

  for(int i=0;i<n;i++){
    ll w,v;
    cin>>w>>v;
    wl[i] = w;
    vl[i] = v;
  }

  ll INF = 1000000000*n+10;
  ll V = 1000*n+10;
  vector<vector<ll>> dp = vector<vector<ll>>(n+1, vector<ll>(V+1, INF));
  dp[0][0] = 0;
  for(int vi=0;vi<V+1;vi++){
    for(int i=0;i<n;i++){
      if(vl[i]>vi){
        dp[i+1][vi] = dp[i][vi];
      }else{
        dp[i+1][vi] = min(dp[i][vi], dp[i][vi-vl[i]]+wl[i]);
      }
    }
  }

  ll res = 0;
  for(ll vi=0;vi<V+1;vi++){
    if(dp[n][vi]<=W){
      res = max(res, vi);
    }
  }
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 80256
N, x = map(int, input().split())
A = list(map(int, input().split()))

cnt = 0
for i in range(N - 1):
    sm = A[i] + A[i+1]
    if sm > x:
        diff = sm - x
        if A[i+1] >= diff:
            A[i+1] -= diff
        else:
            diff2 = diff - A[i+1]
            A[i+1] = 0
            A[i] -= diff2
        cnt += diff

print(cnt)


Measured memory_bytes: 14052
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
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;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
// clang-format on

int x, a, b;

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> x >> a >> b;

  if (abs(x - a) < abs(x - b)) {
    cout << "A" << endl;
  }
  else {
    cout << "B" << endl;
  }
  return 0;
}


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

int main() {
    int N, K;
    int R, S, P;
    cin >> N >> K >> R >> S >> P;
    string T;
    cin >> T;

    for (int i = 0; i < T.size(); i++) {
        if (T[i] == 'r') T[i] = 'p';
        else if (T[i] == 's') T[i] = 'r';
        else if (T[i] == 'p') T[i] = 's';
    }

    int res = 0;
    for (int i = 0; i < T.size(); i++) {
        if (i - K >= 0) {
            if (T[i - K] != T[i]) {
                if (T[i] == 'r') res += R;
                else if (T[i] == 's') res += S;
                else if (T[i] == 'p') res += P;
            } else {
                if (i + K < N) T[i] = '#';
            }
        } else {
            if (T[i] == 'r') res += R;
            else if (T[i] == 's') res += S;
            else if (T[i] == 'p') res += P;
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

char data[100][100];
int n,m;
void p(){
	for(int i=0;i<10;++i){
		for(int j=0;j<10;++j){
			cout << data[i][j];
		}cout << endl;
	}
}

bool check(int a,int b,int c,vector<int> &v){
	
	for(int i=0;i<c;++i){
		bool f = true;
		for(int j=0;j<v.size();++j){
			if(v[j] >= 4){
				v[j] -=4;
				f = false;
				break;
			}
		}
		if(f == true){
			return false;
		}
	}
	
	for(int i=0;i<b;++i){
		bool f = true;
		for(int j=0;j<v.size();++j){
			if(v[j] >= 2){
				v[j] -=2;
				f = false;
				break;
			}
		}
		if(f == true){
			return false;
		}
	}
	
		//not exist
	if(a == 1 &&find(v.begin(),v.end(),1) ==v.end()){
		return false;
	}
	
	return true;
}


int main(){
	map<char,int> ma;
	vector<int> v;
	cin >> n >> m;
	for(int i=0;i<n;++i){
		cin >> data[i];
	}
	
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			char c = data[i][j];
			if(ma.find(c) == ma.end()) ma[c] = 1;
			else ma[c] += 1;
		}
	}
	
	
	for(map<char,int>::iterator itr = ma.begin(); itr != ma.end(); ++itr) {
//		std::cout << "key = " << itr->first << ", val = " << itr->second << "\n";
		v.push_back(itr->second);
    }
	
	
	int a = 0;		//1
	int b = 0;		//2
	int c = 0;		//4
	int tmp = n*m;
	bool f = false;
	bool ff = false;
	if(n%2 == 0) f = true;
	if(m%2 == 0) ff = true;
	
	if(f == false  && ff == false){
		a = 1;
		tmp = tmp -1;
		b = (n-1)/2;
		b+= (m-1)/2;
		tmp = tmp -b*2;
		c = tmp/4;
	}else if(f == true && ff == true){
		c = tmp/4;
	}else{
		int hoge = n;
		if(m%2 == 0) hoge = m;
		b = hoge/2;
		tmp = tmp -2*b;
		c = tmp/4;
		
	}
//	cout << a << " " << b << " " <<c <<endl;
	
	sort(v.begin(),v.end(),std::greater<int>());
	
	if(check(a,b,c,v)) cout << "Yes" <<endl;
	else cout << "No" << endl;
	return 0;
}



Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main {
	BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
	int sum = 0;
	int max = 0;
	int min = 2147483647;
	int dataset = 0;
	int input = 0;
	ArrayList<Integer> output = new ArrayList<Integer>(0);
	public static void main(String []args){
		Main r = new Main();
		r.Run();
	}
	public void Run(){
		try{
			while(true){
				String s = read.readLine();
				dataset = Integer.parseInt(s);
				if(dataset == 0)break;
				sum = 0;
				min = 2147483647;
				max = 0;
				for(int z = 0;z < dataset;z++){
					s = read.readLine();
					input = Integer.parseInt(s);
					sum += input;
					if(input < min)min = input;
					if(input > max)max = input;
				}
				sum -= max+min;
				output.add(sum/(dataset-2));
			}
		}catch(Exception e){
			
		}
		for(int z = 0;z < output.size();z++){
			System.out.println(output.get(z));
		}
	}
}

Measured memory_bytes: 15068
N=int(input())
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
C=[0]+list(map(int, input().split()))

happy=0
for i in range(1, N+1):
  happy+=B[A[i]]
  
for i in range(1, N):
  if A[i]+1==A[i+1]:
    happy+=C[A[i]]
    
print(int(happy))

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

const ll INF = 10e15;

ll dist[205][205];
int N, M, R;

vector<vector<ll>> distforbitDP(10, vector<ll>(10, 0));

ll dp[(1 << 10) + 1][10];
ll rec(int bit, int v) {
    if (dp[bit][v] != -1) return dp[bit][v];

    if (bit == (1 << v)) {
        return dp[bit][v] = 0;
    }

    ll res = INF;

    int prev_bit = bit & ~(1 << v);

    for (int u = 0; u < R; ++u) {
        if (!(prev_bit & (1 << u))) continue;

        if (res > rec(prev_bit, u) + distforbitDP[u][v]) {
            res = rec(prev_bit, u) + distforbitDP[u][v];
        }
    }

    return dp[bit][v] = res;
}

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

    vector<int> r(R);
    rep(i, R) cin >> r[i], --r[i];

    rep(i, N) rep(j, N) dist[i][j] = INF;

    rep(i, M) {
        int a, b, t;
        cin >> a >> b >> t;
        --a;
        --b;
        dist[a][b] = t;
        dist[b][a] = t;
    }

    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
    rep(i, R) rep(j, R) distforbitDP[i][j] = dist[r[i]][r[j]];

    for (int bit = 0; bit < (1 << R); ++bit) {
        for (int v = 0; v < R; ++v) {
            dp[bit][v] = -1;
        }
    }

    ll res = INF;
    for (int v = 0; v < R; ++v) {
        if (res > rec((1 << R) - 1, v)) {
            res = rec((1 << R) - 1, v);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 3980
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans = ans - j - 1 + bisect_left(a, abs(a[i] + a[j]))
print(ans)

Measured memory_bytes: 5344
import java.util.*;
public class Main { 
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String o="";
        int n=sc.nextInt();
        int m=sc.nextInt();
        Point[] points=new Point[n];
        for(int i=0;i<n;i++){
            points[i]=new Point(i);
        }
        
        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            points[a-1].add(b-1);
            points[b-1].add(a-1);
        }
        
        for(int i=1;i<n;i++){
        	if(points[i].list.isEmpty()){
            	System.out.println("No");
                return;
            }
      	}
      
        ArrayList<Point> pointlist=new ArrayList<>();
        pointlist.add(points[0]);
        points[0].mark=0;
      int count=1;
        while(!pointlist.isEmpty()){
            Point point=pointlist.remove(0);
            ArrayList<Integer> list=point.list;
            while(!list.isEmpty()){
                int ind=list.remove(0);
                if(points[ind].mark==Integer.MAX_VALUE){
                    pointlist.add(points[ind]);
                    points[ind].mark=point.ind;
                  	count++;
                }
            }
          	if(count>=n)break;
        }

        int[] ma=new int[n];
        for(int i=0;i<n;i++){
            if(points[i].mark==Integer.MAX_VALUE){
                System.out.println("No");
                return;
            }else{
                ma[i]=points[i].mark+1;
            }
            if(i==n-1)o="Yes";
        }
      System.out.println(o);
      for(int i=1;i<n;i++){
        System.out.println(ma[i]);
      }
    }
    
}

class Point{
    public int mark;
    public int ind ;
    public ArrayList<Integer> list;
    public Point(int ind){
        mark=Integer.MAX_VALUE;
        list=new ArrayList<>();
        this.ind=ind;
    }

    void add(int a){
        list.add(a);
    }
}


Measured memory_bytes: 77496