akhauriyash/Code-Regression huggingface dataset:
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1000000000
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};

struct P{
    int x,y;
};

int main (){
    int n,k;
    cin>>n>>k;
    k--;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    sort(all(v));
    int ans=INT_MAX;
    rep(i,0,n-k){
        ans=min(ans,v[i+k]-v[i]);
    }
    cout<<ans<<endl;
}


/*
5 5
2...2
.....
..1..
.....
2...2

5 10
..3.......
.....1....
..........
....3.....
..........



1010
00000
00000
00000
00000
*/


Measured memory_bytes: 640
import sys
from io import StringIO
import unittest
import os


# 実装を行う関数
def resolve():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    x = input()

    if x == "SUN":
        print(7)
    elif x == "MON":
        print(6)
    elif x == "TUE":
        print(5)
    elif x == "WED":
        print(4)
    elif x == "THU":
        print(3)
    elif x == "FRI":
        print(2)
    elif x == "SAT":
        print(1)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """SAT"""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """SUN"""
        output = """7"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()


Measured memory_bytes: 50156
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
  
using namespace std;
  
#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)
 
#ifdef __BORLANDC__
 
#else
    //#define double __float128
#endif
 
typedef pair<int,int> pii;
  
vector<int> v;
vector<pii> board;
  
bool input(){
    int x,y,z;
    cin>>x>>y>>z;
    if(x==0 && y==0 && z==0)return false;
    v.resize(x);
    board.clear();
    board.resize(y);
    rep(i,x)cin>>v[i];
    rep(i,z){
        int n,a,e;
        cin>>n>>a>>e;
        board[n] = pii(a,e);
    }
    return true;
}
  
const int N = 66;
const int M = N*111;
double dp[N][M][2];
  
double solve(){
      
    rep(i,N)rep(j,M)rep(k,2)dp[i][j][k]=0;
      
    dp[0][0][0]=1;
      
    rep(i,board.size()){
        rep(p, 2){
            int kind = board[i].first;
            int value = board[i].second;
         
            if(kind == 0 || p==1){
                rep(j,v.size()){
                    rep(k,M){
                        dp[i+v[j]][k][0] += dp[i][k][p]*(1.0/v.size());
                    }
                }
            }else{
                if(kind == 1){
                    rep(k,M){
                        dp[i+value][k][1] += dp[i][k][p];
                    }
                }
                if(kind == 2){
                    rep(j,v.size()){
                        rep(k,M-value){
                            dp[i+v[j]][k+value][0] += dp[i][k][p]*(1.0/v.size());
                        }
                    }
                }
                if(kind == 3){
                    rep(j,v.size()){
                        rep(k,M){
                            int pos = max(0, k-value);
                            dp[i+v[j]][pos][0] += dp[i][k][p]*(1.0/v.size());
                        }
                    }
                }
            }
        }
    }
      
    double ret = 0;
    reps(i,board.size(),board.size()+16){
        rep(j,M){
            rep(k,2){
                ret += dp[i][j][k] * j;
            }
        }
    }
    return ret;
}
  
void call(){
    printf("%d\n",int(solve()+1e-9));
}
  
int main(){
    while(input())call();
}

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

void die() {
    cout << "Impossible" << endl;
    exit(0);
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a, a + n);
    if (a[0] != a[1]) {
        for (int i = 1; i < n; ++i) {
            if (a[i] - a[i - 1] > 1) {
                die();
            }
            int j = i;
            while (j < n && a[i] == a[j]) ++j;
            if (j - i < 2) die();
            i = j - 1;
        }
        if (a[n - 1] > 2 * a[0]) die();
    } else {
        if (2 < n && a[0] == a[2]) die();
        for (int i = 2; i < n; ++i) {
            if (a[i] - a[i - 1] > 1) {
                die();
            }
            int j = i;
            while (j < n && a[i] == a[j]) ++j;
            if (j - i < 2) die();
            i = j - 1;
        }
        if (a[n - 1] > 2 * a[0] - 1) die();
    }
    cout << "Possible" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))
#define max(p,q)((p)>(q)?(p):(q))
#define INF ((1LL<<62)-(1LL<<31))

ll s[10010];//1人問題の得点
ll t[10010];//それ以外の得点

int main(){
	ll n,m;
	while(scanf("%lld%lld",&n,&m),n){
		rep(i,1,n+1)s[i]=t[i]=0;
		rep(i,0,m){
			ll ten,k;
			scanf("%lld%lld",&ten,&k);
			ll hito;
			if(k==1){
				scanf("%lld",&hito);
				s[hito]+=ten;
			}else{
				rep(_,0,k){
					scanf("%lld",&hito);
					t[hito]+=ten;
				}
			}
		}
		ll m1=INF,mi,m2=INF;
		rep(i,1,n+1)if(s[i]<m1){
			m1=s[i];
			mi=i;
		}
		rep(i,1,n+1)if(i!=mi&&s[i]<m2)m2=s[i];
		
		ll ans=0;
		rep(i,1,n+1){
			if(i==mi)ans=max(ans,t[i]+s[i]-m2);
			else ans=max(ans,t[i]+s[i]-m1);
		}
		printf("%lld\n",ans+1);
	}
}


Measured memory_bytes: 2044
a,b,c,d=map(int,input().split())
if c>b or a>d:
    print(0)
elif a>=c:
    if b>d:
        print(d-a)
    else:
        print(b-a)
else:
    if b>d:
        print(d-c)
    else:
        print(b-c)

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

int main(){
	string s;
	cin >> s;
  	
  	int ans[s.length()];
  	for(int i=0; i<s.length(); i++)
      ans[i] = 0;
  
  
	int cnt_r = 0, cnt_l = 0;
	int rl_mem;
  	for(int i=0; i<s.length(); i++){      
		if(s[i] == 'R'){
        	cnt_r++;
          	if(s[i+1] == 'L')
              rl_mem = i;
        }
      	else{
        	cnt_l++;
          	if( i==s.length()-1 || s[i+1] != 'L' ){
              	if(cnt_r % 2 == 0){
                	ans[rl_mem] += cnt_r / 2;
                	ans[rl_mem+1] += cnt_r / 2;                  
                }
              	else{
                	ans[rl_mem] += cnt_r / 2 + 1;
                	ans[rl_mem+1] += cnt_r / 2;                 	
                }
              
                if(cnt_l % 2 == 0){
                	ans[rl_mem] += cnt_l / 2;
                	ans[rl_mem+1] += cnt_l / 2;                  
                }
              	else{
                	ans[rl_mem] += cnt_l / 2;
                	ans[rl_mem+1] += cnt_l / 2 + 1;                 	
                }
              
              	cnt_r = 0; cnt_l = 0;
            }
        }
    }
  
   	for(int i=0; i<s.length(); i++)
      cout << ans[i] << " ";
  
  	cout << endl;
  
 	return 0; 
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp make_pair
#define pr(num) cout << num << "\n"
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

int main() {
    ll N;
    string s;
    cin >> N;
    cin >> s;
    ll i, j;
    map<pair<string, string>, ll> mp;
    ll ans=0;
    
    for(i=0; i<1<<N; i++) {
        string a, b;
        for(j=0; j<N; j++) {
            if(i>>j&1) a+=s[j];
            else b=s[j]+b;
        }
        mp[{a, b}]++;
    }
    
    for(i=0; i<1<<N; i++) {
        string a, b;
        for(j=0; j<N; j++) {
            if(i>>j&1) a+=s[j+N];
            else b=s[j+N]+b;
        }
        
        ans+=mp[{b, a}];
    }
    
    pr(ans);
    
    
}


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




int main() {
   #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 string str; 
 cin>>str;
 regex e("(dream|dreamer|erase|eraser)+");
 cout<<((regex_match(str,e))? "YES" : "NO" ) << "\n";
  return 0;
}


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

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} c(2000005);

int main(){
    int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    mint ans =  c(r2+1+c2+1,c2+1) - c(r1+c2+1, c2+1) - c(r2+1+c1, c1) + c(r1+c1,c1);
    cout << ans << endl;
}

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

using namespace std;

int main() {
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    int x=-101,y=101;
    int curr;
    for(int i = 0; i < N; ++i) {
        cin >> curr;
        if(curr > x) x = curr;
    }
    for(int i = 0; i < M; ++i) {
        cin >> curr;
        y = curr < y ? curr : y;
    }
    //cout << x << " " << y << endl;
    if( X < Y && x < y) {
        if(X > x) {
            if(Y <= y) {
                cout << "No War";
            }
            else{
                if(X < y) {
                    cout << "No War";
                }
                else{cout << "War";}
            }
        }
        else{
            if(Y >= y) {
                cout << "No War";
            }
            else{
                if(x < Y) 
                    cout << "No War";
                else {cout << "War";}
            }
        }
    }
    else{cout << "War";}
}


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

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

int H, W;
char m[50][50];
char dx[] = {-1, 0, +1, -1, +1, -1, 0, +1};
char dy[] = {-1, -1, -1, 0, 0, +1, +1, +1};

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

  cin >> H >> W;

  rep(h, H) rep(w, W)
  {
    cin >> m[h][w];
  }

  rep(h, H) rep(w, W)
  {
    if (m[h][w] == '.')
    {
      m[h][w] = '0';
      rep(i, 8)
      {
        if (0 <= w + dx[i] && w + dx[i] < W)
          if (0 <= h + dy[i] && h + dy[i] < H)
            if (m[h + dy[i]][w + dx[i]] == '#')
              m[h][w]++;
      }
    }
  }

  rep(h, H)
  {
    rep(w, W)
    {
      cout << m[h][w];
    }
    cout << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(i):
        res = 1
        for j in to[i]:
            res = res * dfs(j) % md
        return res + 1

    md = 998244353
    n = II()
    xd = LLI(n)
    xd.sort(reverse=True)
    to = [[] for _ in range(n)]
    hp = []
    for i, (x, d) in enumerate(xd):
        while hp and hp[0][0] < x + d:
            px, pi = heappop(hp)
            to[i].append(pi)
        heappush(hp, (x, i))
    ans = 1
    while hp:
        _, i = heappop(hp)
        ans = ans * dfs(i) % md
    print(ans)

main()


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

int main(void){
    int A;
    cin >> A;
    int* card = new int[A];
    
    for (int i = 0; i < A; i++) {
        cin >> card[i];
    }
    
    int Alice, Bob, sum;
  
    Alice = 0;
    Bob = 0;
    sum = 0;
    sort(card,card + A, greater<int>());
    
    for (int i = 0; i < A; i++) {
        if (i % 2 == 0) {
            Alice += card[i];
        } else {
            Bob += card[i];
        }
    }
    delete[] card;
    sum = Alice - Bob;
    cout << sum << endl;
}


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

int main() {
    while (1) {
        int X, Y;
        cin >> X >> Y;
        if (X == 0 && Y == 0) break;
        else {
            if (X < Y) cout << X << " " << Y << endl;
            else cout << Y << " " << X << endl;
        }
    }
}


Measured memory_bytes: 3076
#include<iostream>
#include<string>
using namespace std;
const string day[] = {"Thurs", "Fri", "Satur", "Sun", "Mon", "Tues", "Wednes"};

int main(){
  int m, d;
  while(cin >> m >> d, m != 0 || d != 0) {
    int days = d - 1;
    for(int i = 1; i < m; i++) { 
    if(i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12)  days += 31;
    else if(i == 4 || i == 6 || i == 9 || i == 11) days += 30;
    else days += 29;
    }
    cout << day[days % 7] << "day" << endl;
  }
  return 0;
}
      

Measured memory_bytes: 1196
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> P;
typedef pair<int,P> PP;

int main() {
  int n,m;
  cin >> n >> m;
  PP a[n];
  for(int i=0; i<n; i++) cin >> a[i].F >> a[i].S.F >> a[i].S.S;
  int dp[m+1];
  fill(dp,dp+m+1,0);
  for(int i=0; i<n; i++) {
    int t=1;
    while(a[i].S.S) {
      do {
        for(int j=m; j>=0; j--) {
          if(j+a[i].S.F*t<=m) dp[j+a[i].S.F*t]=max(dp[j+a[i].S.F*t],dp[j]+a[i].F*t);
        }
        a[i].S.S-=t;
      } while(a[i].S.S%(t*2));
      t*=2;
    }
  }
  int ans=0;
  for(int i=0; i<=m; i++) ans=max(ans,dp[i]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3120
use std::cmp;
use std::io::*;
use std::str::FromStr;

fn func(
    v: usize,
    ai: &Vec<i64>,
    graph: &Vec<Vec<usize>>,
    used: &mut Vec<bool>,
    first: bool,
) -> (bool, i64) {
    used[v] = true;
    if !first && graph[v].len() == 1 {
        return (true, ai[v]);
    }
    let mut max: i64 = 0;
    let mut sum: i64 = 0;
    for i in &graph[v] {
        if used[*i] {
            continue;
        }
        let (po, aii) = func(*i, &ai, &graph, used, false);
        if !po {
            return (false, 0);
        }
        max = cmp::max(max, aii);
        sum += aii;
    }
    if sum < ai[v] {
        return (false, 0);
    }
    return (
        cmp::min(sum - max, sum / 2) >= (sum - ai[v]),
        2 * ai[v] - sum,
    );
}

fn main() {
    let n: usize = read();
    let ai: Vec<i64> = (0..n).map(|_| read::<i64>()).collect();
    let mut graph: Vec<Vec<usize>> = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let (a, b) = (read::<usize>() - 1, read::<usize>() - 1);
        graph[a].push(b);
        graph[b].push(a);
    }
    let mut root: usize = 0;
    for i in 0..n {
        if graph[i].len() == 1 {
            root = i;
            break;
        }
    }
    let mut used = vec![false; n];
    let (ok, _) = func(root, &ai, &graph, &mut used, true);
    println!("{}", if ok { "YES" } else { "NO" });
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


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

int main(){
  char c[2][3];
  
  for(int i = 0; i < 2; i++){
    for(int j = 0; j < 3; j++){
      cin >> c[i][j];
    }
  }
  
  if(c[0][0]==c[1][2] && c[0][1]==c[1][1] && c[0][2]==c[1][0]){
    cout << "YES";
  }
  else{
    cout << "NO";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
serach_number = int(input())

def search_prime_number(target):
 
    for i in range(2,serach_number-1 ):
        if target % i == 0:
            return False
    return True

while True:
  if search_prime_number(serach_number):
    print(serach_number)
    break
  serach_number+=1

Measured memory_bytes: 2940
import collections

mod=998244353
n=int(input())
arr=list(map(int,input().split()))
if arr[0]!=0:
  print(0)
else:
  count=collections.Counter(arr)
  if count[0]!=1:
    print(0)
  else:
    ans=1
    for i in range(1,n):
      ans*=pow(count[i-1],count[i],mod)
      ans%=mod
    print(ans)

Measured memory_bytes: 19936
n = int(input())
L = sorted(map(int, input().split()))
d = {}
for i in range(n):
    if L[i] not in d:
        d[L[i]] = 1
    else:
        d[L[i]] += 1
cnt = 0
for k, v in d.items():
    if k == v:
        continue
    else:
        if k > v:
            cnt += v
        else:
            cnt += v - k
print(cnt)


Measured memory_bytes: 18160
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int n;
  cin >> n;
  vector<int> a(n+1);
  vector<int> b(n);
  rep(i,n+1) cin >> a[i];
  rep(i,n) cin >> b[i];
  ll ans = 0;
  rep(i,n){
    if(b[i] < a[i]){
      ans += b[i];
    }
    if(b[i] >= a[i]){
      ans += min(b[i],a[i] + a[i+1]);
      a[i+1] -= b[i] - a[i];
      if(a[i+1] < 0) a[i+1] = 0;
    }
  }
  cout << ans << endl;
}

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

#define INF 12345678900
#define ll long long
#define MOD 1000000007

int N;
ll dp[1010101][2][2];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	dp[0][1][1] = 1;
	for(int i=1; i<=N; i++)
	{
		for(int j=0; j<2; j++)
			for(int k=0; k<2; k++)
			{
				ll &ret = dp[i][j][k];
				ret += 8*dp[i-1][j][k];
				ret += dp[i-1][j|1][k];
				ret += dp[i-1][j][k|1];
				ret %= MOD;
			}
	}
	cout << dp[N][0][0];
	return 0;
}

Measured memory_bytes: 34816
import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def func(q, S):
    ret = 0
    for s in S:
        if q == s:
            ret += 1
        q = '1' if q == '0' else '0'
    return ret


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

    S = list(iss())
    print(min(func('0', S), func('1', S)))


if __name__ == '__main__':
    main()


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

int main() {
    int H1,M1,H2,M2,K;
    cin>>H1>>M1>>H2>>M2>>K;
    int possible=(H2-H1)*60+M2-M1;
    if(K>=possible){
        cout<<0<<endl;
    }
    else{
        cout<<possible-K<<endl;
    }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
 
int main() { 

  int N, l, r, number;
  cin >> N;
  
  
  for (int i = 0; i < N; i++) {
  cin >> l >> r;
  number = number + (r - l + 1);
  }
  cout << number << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define N 100
int main(){
	int A[N], n, v, i, j;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d", A+i);
	}
	for(i=0; i<n; i++){
		v = *(A+i);
		j = i-1;
		while(j >= 0 && *(A+j) > v){
			*(A+j+1) = *(A+j);
			j--;
		}
		*(A+j+1) = v;
		for(j=0; j<n-1; j++){
			printf("%d ", *(A+j));
		}
		printf("%d\n", *(A+j));
	}
    return 0;
}

Measured memory_bytes: 600
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//////////////////////////////////////////////////

// c

int main() {
    ll n, k; cin >> n >> k;
    vector<ll> h(n);
    rep(i,n) cin >> h[i];
    sort(h.begin(), h.end(), greater<ll>());
    ll ans = 0;
    repf(i,k,n) {
        ans += h[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();
        int a_length = a.length();
        int b_length = b.length();
        if(a.charAt(a_length-1) == b.charAt(0) && b.charAt(b_length-1) == c.charAt(0)){
            System.out.println("YES");
            return;
        }
        System.out.println("NO");
    }
}


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

    int main(){
      int n;
      cin >> n;
      vector<int> v(n);
      rep(i,n) cin >> v[i];
      sort(v.begin(),v.end());
      int ans=0;
      for (int i=0;i < n-1;i++){
        ans+=v[i+1]-v[i];
      }
      cout << ans << endl;

      
      return 0;
    }
      
      

Measured memory_bytes: 256
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<cstdio>
#include<climits>

#include<iomanip>
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<string>
#include<queue>
#include<sstream>
#include<map>
#include<set>
#include<utility>
#include<queue>

using namespace std;

int dx[]={1,-1,4,-4};
map<string,int> step;
void bfs(){
  string first = "01234567";
  queue<string> que;
  que.push(first);
  //  step[first] = 0;
  while(!que.empty()){
    string s = que.front();que.pop();

    int izero = s.find('0');
    for(int i = 0;i < 4;i++){
      int nx = izero + dx[i];
      if(!(0 <= nx && nx < 8))continue;
      if(izero == 3 && i == 0)continue;
      if(izero == 4 && i == 1)continue;
      string ns = s;
      swap(ns[izero],ns[nx]);
      if(step.find(ns) != step.end())continue;
      que.push(ns);
      step[ns] = step[s] + 1;
    }
  }
}
int main(){
  ios::sync_with_stdio(false);
  bfs();
  string s;
  while(getline(cin, s)){
    s.erase(remove(s.begin(), s.end(),' '),s.end());
    cout << step[s] << endl;
  }
  return 0;
}

Measured memory_bytes: 3436
#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <map>
#include <bitset>
#include <cmath>
#include <set>

#define INF 1000000000000
#define MOD 1000000007 //10^9+7:合同式の法

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

int main(){
    int N,M,rs=0;
    long double s = 0;
    cin >> N >> M;
    bool fla = false;

    vector<ll> A(N);

    for(int i = 0;i < N;i++){
        cin >> A.at(i);
        s += A.at(i);
    }

    s /= M;
    s /= 4.0;

    sort(A.begin(),A.end());
    reverse(A.begin(),A.end());


    if(A.at(M - 1) >= s)
        cout << "Yes" << endl;
    else
    {
        cout << "No" << endl;
    }
    

}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A , B , M ,S ,H ,J ,I ,count;
  cin >> A >> B;
  count = 0;
  
  for(int x = A; x < B+1; x++){
    M = x;
    S = M % 10000;
    M = M / 10000;
  
    H = S % 1000;
    S = S / 1000;
    
    J = H % 100;
    H = H / 100;
  
    I = J % 10;
    J = J / 10;
    
    if(M == I && S == J){
      count ++;
    }
  }
  cout << count << endl;
  
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using vi = vector<int64_t>;
using vvi = vector<vi>;
using ll = int64_t;
using P = pair<ll,ll>;
ll INF = 1000000007;
// ll INF = 9223372036854775807;
// ll INF = 998244353;

int main() {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    ll n;
    cin >> n;
    vi a(n);
    rep(i,n) cin >> a.at(i);
    ll money = 1000;
    ll amount = 0;
    bool hold = false;
    for(ll i=0; i<n-1; i++){
        if(!hold && a.at(i+1) > a.at(i)){
            amount += money/a.at(i);
            money -= amount*a.at(i);
            hold = true;
        }
        if(hold && a.at(i+1) < a.at(i)){
            money += a.at(i)*amount;
            amount = 0;
            hold = false;
        }
    }
    if(amount > 0) money += a.at(n-1)*amount;
    cout << money << endl;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;

long long mod = 1000000007;

long long div(long long a, long long b, long long c){
    return b / c - (a - 1) / c;
}

int main() {
    int n, max = 0, c = 0, ans = 0;
    string s, t;
    cin >> s >> t;
    //vector<long> as(n);
    map<int, int> cnt;
    for (int i = 0; i < 3; i++){
        if (s[i] == t[i]){
            ans++;
        }
    }
    cout << ans << endl;
}

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

int main() {
    //
    int num;

    cin >> num;

    vector<int> vec(num);
    vector<int> vec2;
    for (int i = 0; i < num; i++) cin >> vec.at(i),vec.at(i)--;

    for (int i = 0; i < num; i++) {
        int ans = -1;
        for (int j = vec.size() - 1; j >= 0; j--) {
            if (vec.at(j) == j) {
                ans = j;
                break;
            }
        }

        if (ans == -1) {
            cout << ans;
            return 0;
        }

        vec2.push_back(ans + 1);
        vec.erase(vec.begin() + ans);
    }

    reverse(vec2.begin(), vec2.end());
    for (int i = 0; i < vec2.size(); i++) cout << vec2.at(i) << endl;
    //
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;//typo用
using uintl = unsigned long long;
using itn = int;//typo用
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a) - 1; i >= (intl)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl//1次元配列の出力
#define rrdebug(i, j, x) rep(i, alength(x))rep(j, alength(x[i]))cout << #x << "[" << i << "][" << j << "]:" << x[i][j] << endl//二次元配列の出力
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = acos(-1);
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) {a = b; return true;} return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) {a = b; return true;} return false; }
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl kai(intl k){//k!を求める関数,
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl digit10(intl a){//aを10進数で表したときの桁数を求める関数
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}

signed main(){
    cout << fixed << setprecision(10);
    
    intl n;
    cin >> n;
    intl a[n];
    rep(i,n)cin >> a[i];
    intl q;
    cin >> q;
    intl b[q],c[q];
    rep(i,q)cin >> b[i] >> c[i];
    map<intl,intl> m;
    intl cnt = 0;
    rep(i,n){
        cnt += a[i];
        m[a[i]]++;
    }
    rep(i,q){
        intl num = m[b[i]];
        cnt -= (num * b[i]);
        cnt += (num * c[i]);
        m[b[i]] = 0;
        m[c[i]] += num;
        cout << cnt << endl;
    }
    return 0;
}


Measured memory_bytes: 11716
//abc139_a.cpp
//Sun Sep  1 20:53:23 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	string s,t;
	cin >> s >> t;

	int ans = 0;
	for (int i=0;i<3;i++){
		if (s[i]==t[i]){
			ans++;
		}
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 256
//temprates
#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

using ll = long long;
using namespace std;

#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)
#define LFOR(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
#define FORR(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define LFORR(i,a,b) for(ll i = (int)(a); i >= (ll)(b); i--)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define LREP(i,n) LFOR(i,0,(ll)(n)-1)
#define REPR(i,n) FORR(i,(int)(n)-1,0)
#define LREPR(i,n) LFORR(i,(ll)(n)-1,0)

#define SIZ(v) int(v.size())
const int INF = 1e8;
const ll LINF = 1e15;
const int MOD = 1e9+7;




int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  vector<int> l;
  int d,n,x,ans=1;
  cin >> n >> x;
  REP(i,n){
    int k;
	cin >> k;
    l.push_back(k);
}
  REP(i,n){
    d += l[i];
    if(d>x) break;
    ans++;}
  cout << ans << endl;}
    


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

int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> mn, mx;
	f(i, 0, n){
		int t;
		scanf("%d", &t);
		if (t < 0)mn.push_back(t);
		else mx.push_back(t);
	}
	reverse(mn.begin(), mn.end());
	int an = 1e9;
	if (k <= (int)mn.size())an = -mn[k - 1];
	if (k <= (int)mx.size())an = min(an, mx[k - 1]);
	f(i, 0, mx.size()){
		int j = k - (i + 1) - 1;
		if (j < 0 || j >= (int)mn.size())continue;
		an = min(an, mx[i] * 2 - mn[j]);
	}
	f(i, 0, mn.size()){
		int j = k - (i + 1) - 1;
		if (j < 0 || j >= (int)mx.size())continue;
		an = min(an, -mn[i] * 2 + mx[j]);
	}
	printf("%d\n", an);
}

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

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair

int n;

string s;

map <pair <string, string>, int> ma;

int main() {
  cin >> n >> s;
  int N = (1 << n);
  REP(mask, N) {
    string a = "";
    string b = "";
    REP(i, n) {
      if (mask & (1 << i)) a += s[i];
      else b += s[i];
    }
    reverse(all(b));
    ma[{a, b}]++;
  }
  ll sol = 0;
  REP(mask, N) {
    string a = "";
    string b = "";
    REP(i, n) {
      if (mask & (1 << i)) a += s[n + i];
      else b += s[n + i];
    }
    reverse(all(b));
    sol += ma[{b, a}];
  }
  cout << sol << endl;
  return 0;
}


Measured memory_bytes: 87040
program prob3
    implicit none
    integer::N, i, j
    integer, allocatable::a(:)
    integer(16)::ans
    read(*,*) N
    allocate(a(3*N))
    read(*,*) a
    call heapsort(3*N,a)
    ans = 0
    do i = 3*N-1, N+1, -2
        ans = ans + a(i)
    end do
    write(*,*) ans
    stop
contains
    subroutine heapsort(n,array)
        implicit none
        integer,intent(in) :: n
        integer,intent(inout) :: array(1:n)
    
        integer ::i,k,j,l
        double precision :: t
    
        if(n.le.0)then
        write(6,*)"Error, at heapsort"; stop
        endif
        if(n.eq.1)return
    
        l=n/2+1
        k=n
        do while(k.ne.1)
        if(l.gt.1)then
            l=l-1
            t=array(L)
        else
            t=array(k)
            array(k)=array(1)
            k=k-1
            if(k.eq.1) then
                array(1)=t
                exit
            endif
        endif
        i=l
        j=l+l
        do while(j.le.k)
            if(j.lt.k)then
                if(array(j).lt.array(j+1))j=j+1
            endif
            if (t.lt.array(j))then
                array(i)=array(j)
                i=j
                j=j+j
            else
                j=k+1
            endif
        enddo
        array(i)=t
        enddo
        return
    end subroutine heapsort
end program

Measured memory_bytes: 4272
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int R = sc.nextInt();
    int n = R;
    
    if (N < 10) {
      n = R + (100 * (10 - N));
    }
    
    System.out.println(n);
  }
}

Measured memory_bytes: 23764
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

#define FOR(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define REP(i, n) FOR((i), 0, (n))

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

bool is_palindrome(string s){
    int n = s.size();
    int i=0,j=n-1;
    while(i < j){
        if(s[i] != s[j])
            return false;
        i++, j--;
    }
    return true;
}
int main() {
    string s;
    cin >> s;
    int n = s.size();
    if(!is_palindrome(s)){
        cout << "No" << endl;
    }
    else if(!is_palindrome(s.substr(0, (n-1)/2)) || !is_palindrome(s.substr((n+1)/2, (n-1)/2))){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <set>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long LL;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)

int main(){
    int N;
    cin >> N;
    vector<LL> A(N);
    REP(i,N)cin>>A[i];

    LL sum = 0;
    
    REP(i,N){
        LL pre = (i==0)? 0: A[i-1];
        sum += abs(A[i] - pre);
    }
    sum += abs(A[N-1] - 0);

    REP(i,N){
        LL pre = (i==0)? 0: A[i-1];
        LL next = (i==N-1)? 0: A[i+1];

        LL ans = sum - abs(A[i] - pre) - abs(next - A[i]) + abs(next - pre);
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 4056
#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}

int main()
{
	dhoom;
	int x , b , c;
	cin >> x >> b >> c;
	int a[] = { x , b , c};
	sort( a, a + 3);
	cout << a[1] - a[0] + a[2] - a[1] << endl; 
	return 0;
} 



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

#define ll long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define vi vector<int>
#define vl vector<long long>
#define sz size()
#define x first
#define y second
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;  

ll n, k, ans;
ll a[200200], p[200200], t[800800];
vl v;

void upd(int v, int tl, int tr, int pos) {
	if(pos > tr || pos < tl) return;
	if(tl == tr) {
		t[v]++;
		return;
	}
	int mid = (tl + tr) >> 1;
	upd(v + v, tl, mid, pos);
	upd(v + v + 1, mid + 1, tr, pos);
	t[v] = t[v + v] + t[v + v + 1];
}
ll get(int v, int tl, int tr, int l, int r) {
	if(tl > r || l > tr) return 0;
	if(tl >= l && tr <= r) return t[v];
	int mid = (tl + tr) >> 1;
	return get(v + v, tl, mid, l, r) + get(v + v + 1, mid + 1, tr, l, r);
}

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

	for(int i = 1; i <= n; i++) {
		p[i] = a[i];
		p[i] += p[i-1];
		v.pb(-k * i + p[i]);
	}

	v.pb(0);
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());

	int j = upper_bound(v.begin(), v.end(), 0) - v.begin();
	upd(1, 1, n, j);
	
	for(int i = 1; i <= n; i++) {
		ll cur = - k * i + p[i];
		int j = upper_bound(v.begin(), v.end(), cur) - v.begin();
		ans += get(1, 1, n, 1, j);
		upd(1, 1, n, j);
	}

	printf("%lld", ans);

	return 0;
}

Measured memory_bytes: 11376
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
int n,k,a[maxn],pos;
inline int getint(){
	char c=getchar();bool p;int x;x=p=0;
	while((c<'0'||c>'9')&&c!='-')c=getchar();
	if(c=='-')p=1,c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	if(p)x=-x;return x;
}
void init(){
	n=getint(),k=getint();
	for(int i=1;i<=n;++i){
		a[i]=getint();
		if(a[i]==1)pos=i;
    }
}
void solve(){
	int ans=0;
	for(int i=1;i<n;i+=(k-1))++ans;
	printf("%d\n",ans);
}
int main(){
	init();
	solve();
	return 0;
}

Measured memory_bytes: 1016
#include <stdio.h>
void buildMaxHeap(void);
void maxHeapify(int );
int left(int );
int right(int );
int heap_size;
int A[500005];
int main() {
	int i;
	scanf("%d",&heap_size);
	for(i=1;i<=heap_size;i++) {
		scanf("%d",&A[i]);
	}
	buildMaxHeap();
	for(i=1;i<=heap_size;i++) {
		printf(" %d",A[i]);
	}
	printf("\n");
	return 0;
}

int left(int i) { return 2*i; }
int right(int i) { return 2*i+1; }

void buildMaxHeap(void) {
	int i;
	for(i= heap_size/2;i>=1;i--) {
		maxHeapify(i);
	}
}

void maxHeapify(int i) {
	int l,r,temp,largest=0;
	l = left(i);
	r = right(i);
	if( l <= heap_size && A[l] > A[i] ) largest = l;
	else largest = i;
	if( r <= heap_size && A[r] > A[largest] ) largest = r;
	if(largest != i) {
		temp = A[i];
		A[i] = A[largest];
		A[largest] = temp;
		maxHeapify(largest);
	}
}

Measured memory_bytes: 2548
#include<bits/stdc++.h>
using namespace std;
#define SC scanf
#define PR printf
#define pb push_back
#define mp make_pair
#define SZ(v) ((int)(v).size())
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef pair<pii,pii> ppp;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef map<int,int> mii;
const int INF=0x3f3f3f3f;
const ll LL_INF=0x3f3f3f3f3f3f3f3f;
const int xx[4]={1,-1,0,0};
const int yy[4]={0,0,1,-1};
int inline nextin(){
	int t;
	if(scanf("%d",&t)!=1)exit(0);
	return t;
}
int inline in(){
	int x=0,c;
	for(;(uint)((c=getchar())-'0')>=10;){
		if(c=='-')return -in();
		if(!~c)throw ~0;
	}
	do{
		x=(x<<3)+(x<<1)+(c-'0');
	}while((uint)((c=getchar())-'0')<10);
	return x;
}
int main(){
    cin.sync_with_stdio(false);cin.tie(0);
	int a,b;
	cin>>a>>b;
	cout<<max(max(a+b,a-b),a*b)<<endl;
	return 0;
}


Measured memory_bytes: 256
def rec(cards, head)
  if cards.size > 0
    if cards.count(cards[0]+1) > 0 and cards.count(cards[0]+2) > 0
      cards_toitsu = Marshal.load(Marshal.dump(cards))
      cards_toitsu.delete_at(cards_toitsu.index(cards[0]+2))
      cards_toitsu.delete_at(cards_toitsu.index(cards[0]+1))
      cards_toitsu.shift
      return true if rec(cards_toitsu, head)
    end
    if cards[0] == cards[1] and head
      cards_head = Marshal.load(Marshal.dump(cards))
      2.times{cards_head.shift}
      return true if rec(cards_head,false)
    end
    if cards[0] == cards[1] and cards[0] == cards[2]
      cards_syuntsu = Marshal.load(Marshal.dump(cards))
      3.times{cards_syuntsu.shift}
      return true if rec(cards_syuntsu, head)
    end
  elsif cards.size == 0
    return true 
  end
end

while gets
  t = $_.chomp.split('').map(&:to_i).sort
  ans = []
  1.upto(9) do |i|
    tt = (Marshal.load(Marshal.dump(t)) << i).sort
    unless (tt.count(i) == 1 and tt.count([i-1,0].max) == 0 and tt.count([i+1,9].min) == 0) or tt.count(i) > 4 then
      ans << i if rec(tt,true)
    end
  end
  puts ans.empty? ? 0 : ans.join(" ")
end

Measured memory_bytes: 9016
a, b, c, d = map(int, input().split())
ans = 0
if a < c and c < b:
    if b < d:
        ans += b-c
    else:
        ans += d-c
elif c < a and a < d:
    if d < b:
        ans += d-a
    else:
        ans += b-a
elif a == c:
    if b < d:
        ans += b-a
    else:
        ans += d-a
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;

int main(){
    ll X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<ll> x(X), y(Y), z(Z);
    for (int i = 0; i < X;i++)cin >> x[i];
    for (int i = 0; i < Y;i++)cin >> y[i];
    for (int i = 0; i < Z;i++)cin >> z[i];

    vector<unsigned long long> xy(X * Y);
    for (int i = 0; i < X;i++){
        for (int j = 0; j < Y;j++)
            xy[i * X + j] = x[i] + y[j];
    }
    sort(xy.begin(), xy.end());
    if(X * Y > K){
        vector<unsigned long long> xyz(0);
        for (int i = 0; i < K;i++){
            for (int j = 0; j < Z;j++)
                xyz.emplace_back(xy[X * Y - i - 1] + z[j]);
        }
        sort(xyz.begin(),xyz.end());
        for (int i = 0; i < K;i++)
            cout << xyz[xyz.size() - i - 1] << endl;
    }else
    {
        vector<unsigned long long> xyz(0);
        for (int i = 0; i < X*Y; i++)
        {
            for (int j = 0; j < Z; j++)
                xyz.emplace_back(xy[X * Y - i - 1] + z[j]);
        }
        sort(xyz.begin(), xyz.end());
        for (int i = 0; i < min(K,X*Y*Z); i++)
            cout << xyz[xyz.size() - i - 1] << endl;
    }
    
    return 0;
}

Measured memory_bytes: 42984