akhauriyash/Code-Regression huggingface dataset:
public class
Main
{
  public static void
  main (
    String[ ] args
    )
  {
    java.util.Scanner cin = new java.util.Scanner ( System.in );
    int n;

    for ( n = cin.nextInt ( ); n != 0; --n )
    {
      int[ ] a = { cin.nextInt ( ), cin.nextInt ( ), cin.nextInt ( ) };

      java.util.Arrays.sort ( a );
      System.out.println ( a[ 0 ] * a[ 0 ] + a[ 1 ] * a[ 1 ] == a[ 2 ] * a[ 2 ]
        ? "YES" : "NO" );
    }

    return ;
  }
}

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

int main() {
  string b;
  cin >> b;
  for(int i = 0; i < b.size(); i++) {
    if(b.at(i) == 'A')
      cout << 'T';
    if(b.at(i) == 'T')
      cout << 'A';
    if(b.at(i) == 'C')
      cout << 'G';
    if(b.at(i) == 'G')
      cout << 'C';
  }
  cout << endl;
}

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

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()

#define MOO(i, a, b) for (int i=a; i<b; i++)
#define M00(i, a) for (int i=0; i<a; i++)
#define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define M00d(i,a) for (int i = (a)-1; i >= 0; i--)

#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define _<< " _ " <<

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

const ll MOD = 1e9+7;

int main() { FAST
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ll n, k;
	ll ans = 0;
	cin >> n >> k;

	//0 to n
	for(int i = k; i <= n+1; i++) {
		ll bot = 0, top = 0;
		bot = ((i-1) * i) / 2;
		top = bot + (i * (n - (i-1)));
		ans += top - bot + 1;
		ans %= MOD;
	}
	finish(ans);
}


Measured memory_bytes: 3656
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        ModScanner ms = new ModScanner();
        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);
        String s = ms.nextToken();
        String t = ms.nextToken();

        int[][] dp = new int[s.length() + 1][t.length() + 1];
        int i, j;
        for (i = 1; i <= s.length(); i++) {
            for (j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder lcs = new StringBuilder();
        for (i = s.length(), j = t.length(); i > 0 && j > 0; ) {
            if (dp[i][j] == dp[i - 1][j - 1] + 1 && dp[i][j] != dp[i - 1][j] && dp[i][j] != dp[i][j - 1]) {
                lcs.insert(0, s.charAt(i - 1));
                j--;
            } else if (dp[i][j - 1] > dp[i - 1][j]) {
                j--;
            } else {
                i--;
            }
        }

        while (j > 0) {
            if (s.charAt(i) == t.charAt(--j)) {
                lcs.insert(0, s.charAt(i));
            }
        }

        out.println(lcs.toString());
        out.close();
    }
}

class ModScanner {

    BufferedReader br;
    StringTokenizer st;

    public ModScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String nextToken() throws Exception {
        while (st == null || !st.hasMoreElements()) {
            st = new StringTokenizer(br.readLine());

        }
        return st.nextToken();
    }

    String nextString() throws Exception {
        return br.readLine();
    }


    int nextInt() throws Exception, Exception {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

}


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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
    return string(1, val);
}

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

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

using namespace std;

int N;
int input[100001];

int main() {
	int ans = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> input[i];
	}
	for (int i = 1; i <= N;) {
		if (i != input[i]) {
			i++;
			continue;
		}
		if (i == N && input[i] == i) {
			ans++;
			break;
		}
		if (i == input[i]) {
			swap(input[i], input[i + 1]);
			ans++;
			i += 2;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define SaveTime ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define mx *max_element
#define mi *min_element
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
const int N = 1e6+5;
const int INF = 1e18L;
int ncr(int n,int r){if(n<r)return 0;int p=1,k=1;if(n-r<r)r=n-r;if(r!=0){while(r){p*=n;k*=r;int g=__gcd(p, k);p/=g;k/=g;n--;r--;}}else p=1;return p;}
#define pi acos(-1)
int ar[N];
int tree[2*N];
int dp[N];
int bit[N];
signed main(){
 
	SaveTime;
	int T=1;
	// cin >> T;
	while(T--){
		int n;
		cin >> n ;
		n--;
		int ans = (n*(n+1))/2;
		cout << ans << endl;
	
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

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

    int n;
    cin >> n;
    deque<int> dq;
    int a;
    for(int i=0;i<n;i++){
    	cin >> a;
    	if(i&1) dq.push_front(a);
    	else dq.push_back(a);
    }
    vector<int> v;
    if(n&1){
    	while(!dq.empty()){
    		v.pb(dq.back());
    		dq.pop_back();
    	}
    }
    else{
    	while(!dq.empty()){
    		v.pb(dq.front());
    		dq.pop_front();
    	}
    }
    for(int i: v)cout << i << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3960
#include <fstream>
#include <vector>
#include <iostream>

// BE CAREFUL WITH HASH TABLE & UNORDERED MAP
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;

#define MOD 998244353
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = (b-1); i >= (a); i--)
#define RF0(i,b) RFO(i,0,b)
#define ll long long
#define pii pair<int,int>
#define add(a,b) ((int) (((ll) (a) + (b))%MOD))
#define mul(a,b) ((int) (((ll) (a) * (b))%MOD))
#define PB emplace_back
#define MP make_pair
#define F first
#define S second

// ifstream cin ("cinput.in");
// ofstream cout ("coutput.out");

int N,a,b;
ll edges = 0;
vector<int> graph [200000];

void dfs(int node, int par) {
    for (int ne: graph[node]) {
        if (ne == par) continue;
        edges += (ll) (min(node,ne)+1) * (ll) (N-max(node,ne));
        dfs(ne, node);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    F0R(i,N-1) {
        cin >> a >> b;
        a--; b--;
        graph[a].PB(b);
        graph[b].PB(a);
    }
    dfs(0,-1);
    ll sum = 0;
    F0R(i,N) sum += (ll) (N-i) * (ll) (i+1);
    cout << sum-edges << '\n';
}

Measured memory_bytes: 23828
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

using namespace std;

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    int c;
    int sum;
    int ans=0;
    
    for (int i = 1; i <= n; ++i){
        sum=0;
        c=i;
        while(c >= 1){
            sum += c%10;
            c=c/10;
        }
        if(a<=sum && sum<= b) ans+=i;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if 0 in A:
	print(0)
	exit()
	
ans = 1
for a in A:
	ans *= a
	if ans > 10**18:
		print(-1)
		break
else:
	print(ans)


Measured memory_bytes: 23484
#include<cstdio>
#include<cstring>
#define MOD 1000000007LL

typedef long long int lli;

lli inv(lli a) {
    lli res=1;
    lli b=MOD-2;
    while(b) {
        if(b%2) res*=a%MOD;
        a*=a%MOD;
        a%=MOD;
        b/=2;
        res%=MOD;
    }
    return res;
}

lli comb(lli a, lli b) {
    lli res = 1;
    for(lli i=0; i<b; a--, i++)
        res *= a%MOD, res %= MOD;
    for(lli i=1; i<=b; i++)
        res *= inv(i), res %= MOD;
    return res%MOD;
}

int main(void) {
    int h,w,a,b;
    scanf("%d%d%d%d",&h,&w,&a,&b);
    lli res = comb(h+w-2,h-1);
    lli p = comb(h-a-1,0), q = comb(w-1+a-1, w-1);
    for(int i=0; i<b; i++) {
        res -= p*q;
        res += MOD*MOD;
        res %= MOD;
        p*=(h-a-1+i+1) %MOD, p%=MOD, p+=MOD, p%=MOD;
        p*=inv(i+1) %MOD, p%=MOD, p+=MOD, p%=MOD;
        q*=inv(w-i-1+a-1) %MOD, q%=MOD, q+=MOD, q%=MOD;
        q*=(w-i-1) %MOD, q%=MOD, q+=MOD, q%=MOD;

    }
    printf("%lld\n",res);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int n, m, q; cin >> n >> m >> q;
	std::vector<std::vector<int>> vec(n);
	for(int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		
		vec[a - 1].push_back(b - 1);
	}
	for(int i = 0; i < n; i++) sort(begin(vec[i]), end(vec[i]));
	
	for(int i = 0; i < q; i++) {
		int a, b; cin >> a >> b;
		
		int count = 0;
		for(int j = a - 1; j < b; j++) {
			count += lower_bound(begin(vec[j]), end(vec[j]), b) - begin(vec[j]);
		}
		
		cout << count << endl;
	}
	
	return 0;
}


Measured memory_bytes: 2176
#include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <set>
    #include <algorithm>
    #include <vector>
    #include <stack>
    #include <queue>
    #include <cstring>
    #include <string>
    using namespace std;
    typedef long long ll;
    const int N=200000+10;
    int n,k,dp[N],h[N];
    int main()
    {
        //freopen("a.in","r",stdin);
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>h[i];
        memset(dp,0x3f,sizeof(dp));
    	dp[1]=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=k;j++){
    			if(i+j<=n)dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]));
    		}
    	}
    	cout<<dp[n]<<"\n";
        return 0;
    }

Measured memory_bytes: 1408
n = int(input())
h = list(map(int,input().split()))

c = []
c.append(0)
c.append(abs(h[1]-h[0]))


for i in range(2,n):
    c.append(min(c[i-2]+abs(h[i]-h[i-2]),c[i-1]+abs(h[i]-h[i-1])))


print(c[n-1])

Measured memory_bytes: 89828
n,m = map(int,input().split())
h = list(map(int,input().split()))
#h.sort()
l = [[] for _ in range(n)]

for i in range(m):
  a,b = map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

c = 0
for j in range(n):
  if len(l[j]) == 0:
    c += 1
  else:
    m = 0
    for k in l[j]:
      if h[j] <= h[k]:
        m = 1
        break
    if m == 0:

      c += 1
      
print(c)
  

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

int main() {
  int N;
  cin >> N;
  vector<int> light(N);
  int a;
  for(int i = 0; i< N ; i++){
  	cin >> a;
    light.at(i) = a;
  }
  int count = 1;
  int check = 0;
  int next = 0;
  for(int i = 0; i < N ; i++){
  	if(light.at(next) == 2){
      check = 1;
      break;
    }
    else{
      count++;
    }
    next = light.at(next) - 1;
  }
  if(check == 1){
    cout << count << endl;
  }else{
  	cout << -1 << endl;
  }
}


Measured memory_bytes: 3784
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

long long gcd(long long a, long long b) {
  long long _max = a > b ? a : b;
  long long _min = a > b ? b : a;
  if (!(_max%_min)) return _min;
  else return gcd(_min, _max%_min);
}
 
long long lcm(long long a, long long b) {
  return a/gcd(a,b)*b;
}

const string YES = "Yes";
const string NO = "No";

void solve(long long N, std::vector<long long> A){
    long long nodd=0l, n2=0l, n4=0l;
    for(auto a:A){
        if(a%4==0)n4++;
        else if(a%2==0)n2++;
        else nodd++;
    }
    if(n2==0 && nodd-n4==1)cout << YES << endl;
    else if(nodd>n4)cout << NO << endl;
    else cout << YES << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&a[i]);
    }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main(void){
	int d,i;
	double area;

	for(;;){
		area = 0;
		if(scanf("%d",&d) == EOF){
			break;
		}
		for(i = 1 ; i < (600 / d) ; i ++){
			area += (i * d) * (i * d)  * d;
		}
		printf("%.0lf\n",area);
	}
	return 0;
}

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

ull f(ull x) {
    if (x % 4 == 0) return x;
    else if (x % 4 == 1) return 1ULL;
    else if (x % 4 == 2) return (1ULL ^ x);
    else return 0ULL;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    #ifdef DEBUG
        freopen("in.txt", "r", stdin);
    #endif
    
    ull a, b; cin >> a >> b;
    cout << (f(a) ^ f(b) ^ a) << '\n';

    return 0;
}


Measured memory_bytes: 384
#include<map>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
double n;
string s;
int main(){
	cin>>n;
	cout<<(n+1)*n/2;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll m, sum = 0;
int main()
{
	cin >> m;
	for (int i = 1; i < m; i++)
	{
		if (m % i == 0) {
			sum += ((m / i) - 1);
		}
		else {
			sum += (m / i);
		}
	}
	cout << sum << endl;
}

Measured memory_bytes: 3628
#include <iostream>
using namespace std;
 
int main(){
	int N,M;
	cin >> N >> M;
 
	int a[N];
  	double sum = 0;
 
	for(int i = 0 ; i < N ; i++){
		cin >> a[i];
        sum += a[i];
	}
 
	int cnt = 0;
	for(int i = 0; i < N ; i++){
		if((double)a[i] >= sum*(1/(4*(double)M))){
			cnt ++;
		}
	}
 
	if(cnt >= M){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
    
    return 0;
}

Measured memory_bytes: 256
n = int(input())
k = int(input())
import math
def k1(n):
    if n < 10:
        ans = n
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = 9 * (len(n1) - 1) + n2
    return int(ans)

def k2(n):
    if n < 100:
        ans = n - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (81 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 3)) / 2) +  (n2 - 1) * k1(10 ** (len(n1) - 1) - 1) + k1(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

def k3(n):
    if n < 1000:
        ans = n - k2(n) - k1(n)
    else:
        n1 = str(n)
        n2 = int(n1[0])
        ans = (729 * (math.factorial(len(n1) - 1) / math.factorial(len(n1) - 4)) / 6) + (n2 - 1) * k2(10 ** (len(n1) - 1) - 1) + k2(n - n2 * 10 ** (len(n1) - 1))
    return int(ans)

if k == 1:
    print(k1(n))
elif k == 2:
    print(k2(n))
else:
    print(k3(n))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,X,Y;
  cin>>N>>X>>Y;
  --X; --Y;
  vector<vector <int>> dist(N,vector<int>(N,-1));
  
  for(int s=0; s<N; s++){
    queue<int> que;
    que.push(s);
    dist[s][s]=0;
    while(!que.empty()){
      auto v=que.front(); que.pop();
      vector<int> nvs;
      if (v>0) nvs.push_back(v-1);
      if (v<N-1) nvs.push_back(v+1);
      if (v==X) nvs.push_back(Y);
      if (v==Y) nvs.push_back(X);
      for (auto nv:nvs){
        if (dist[s][nv]==-1){
          dist[s][nv]=dist[s][v]+1;
          que.push(nv);
        }
      }
    }
  }
  
  vector <int> res(N,0);
  for (int i=0; i<N; i++){
    for(int j=i+1; j<N; j++) res[dist[i][j]]++;
  }
  for (int d=1;d<N; d++)cout<<res[d]<<endl;
}
  
       

Measured memory_bytes: 16000
import sys
fin = sys.stdin.readline
sys.setrecursionlimit(200000)

def factorial(n, mod):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1, mod) % mod


MOD = 10**9 + 7
N = int(fin())
A_list = [int(elem) for elem in fin().split()]

fac_N = factorial(N, MOD)
inv_nums = [fac_N * pow(i, MOD - 2, MOD) % MOD for i in range(1, N + 1)]
cuml_inv_nums = [inv_nums[0]]
for inv_num in inv_nums[1:]:
    cuml_inv_nums.append((cuml_inv_nums[-1] + inv_num) % MOD)

ans = 0
for i, A in enumerate(A_list):
    ans += A * (cuml_inv_nums[i] + cuml_inv_nums[N - 1 - i] - cuml_inv_nums[0]) % MOD
    ans %= MOD

print(ans)



Measured memory_bytes: 126104
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    string w[n];
    char a,b;
    bool isOk = true;
    cin >> w[0];
    for(int i=1;i<n;i++){
        cin >> w[i];
        a =w[i].front();
        b =w[i-1].back();
        if(a != b){
            isOk = false;
            break;
        }
        for(int j=0;j<i;j++){
            if(w[i]==w[j]){
                isOk = false;
                i=n;
                j=i;
            }
        }
        
    }
    if(isOk){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


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


vector<int>to[200005];
vector<int>ans;

 void dfs(int v,int p=-1){

   for(int u:to[v])
  {
   if(u == p){
    continue;
     }

     ans[u] += ans[v];
     dfs(u,v);
  }


 }

int main(){

 int n,Q;
 cin>>n>>Q;

  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
     a--;
     b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  ans.resize(n);
  for(int i=0;i<Q;i++)
 {
    int p,x;
     cin>>p>>x;
     p--;
     ans[p] += x;
  }

  dfs(0);
  for(int i=0;i<n;i++){
    cout<<ans[i]<<" ";
  }

    cout<<endl;

 return 0;
}






Measured memory_bytes: 23552
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for (int i = 0; i<(n); i++)
#define in(n) cin >> (n)
#define out(ans) cout << (ans) << endl;
using ll = int64_t;
using v = vector<int>;

int64_t siguma(int64_t start, int64_t goal) {
  // startからgoalまでの自然数の和を返す
  
  if (start==0) start++;
  int64_t ans;
  
  // 最も手っ取り早い計算
  //ans = goal*(goal+1)/2 - (start-1)*start/2;
  
  // オーバーフローさせないように組んだ
  
  if (start % 2 == 0 && goal % 2 == 0) {
    ans = goal/2 * (goal+1) - start/2 * (start-1);
  }
  else if (start % 2 == 0 && goal % 2 != 0) {
    ans = (goal+1)/2 * goal - start/2 * (start-1);
  }
  else if (start % 2 != 0 && goal % 2 == 0) {
    ans = goal/2 * (goal+1) - (start-1)/2 * start;
  }
  else {
    ans = (goal+1)/2 * goal - (start-1)/2 * start;
  }
  
  return ans;
}

int main() {
  ll N, K;
  ll ans = 0;
  in(N);
  in(K);
  
  for (ll i = K; i <= N+1; i++) {
    ll plus;
    plus = siguma(N-i+1, N) - siguma(0, i-1) + 1;
    ans += plus;
  }
  
  ans = (ans % 1000000007);
  out(ans);
}

Measured memory_bytes: 3632
import Data.Char
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as BS

main :: IO()
main = getLine >> (print . solve =<< getIntList)

solve :: [Int] -> Int
solve = sum . (zipWith ((max 0.).flip (-)) =<< (0:))

-- IO
readInt :: BS.ByteString -> Maybe (Int, BS.ByteString)
readInt = BS.readInt . BS.dropWhile isSpace

getIntList :: IO [Int]
getIntList = unfoldr readInt <$> BS.getLine

Measured memory_bytes: 508
IDENTIFICATION DIVISION.
PROGRAM-ID. aising-C.
DATA DIVISION.
*>
WORKING-STORAGE SECTION.
01 N          PIC  9(05) COMP.
01 I          PIC  9(04) COMP.
01 X          PIC  9(04) COMP.
01 Y          PIC  9(04) COMP.
01 Z          PIC  9(04) COMP.
01 V          PIC  9(09) COMP.
01 TBL.
   03 T       PIC  9(03) OCCURS 10000.
01 OUT        PIC  ZZ9.
*>
PROCEDURE DIVISION.
  ACCEPT N.
*>
  MOVE ZERO TO TBL.
  PERFORM VARYING X FROM 1 BY 1 UNTIL X > 100
    PERFORM VARYING Y FROM 1 BY 1 UNTIL Y > 100
      PERFORM VARYING Z FROM 1 BY 1 UNTIL Z > 100
        COMPUTE V = X * X + Y * Y + Z * Z + X * Y + Y * Z + Z * X
        IF V <= 10000
          ADD 1 TO T(V)
        END-IF
      END-PERFORM
    END-PERFORM
  END-PERFORM.
*>
  PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
    MOVE T(I) TO OUT
    DISPLAY FUNCTION TRIM(OUT)
  END-PERFORM.
*>
  STOP RUN.


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

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4");
            WillReturn.Add("6 5 6 8");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("4 5 3 5 4");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("9 5 6 8 4");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] HArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int CurrMax = int.MinValue;
        int Answer = 0;
        foreach (int EachInt in HArr) {
            if (CurrMax <= EachInt) {

                Answer++;
                CurrMax = EachInt;
            }
        }
        Console.WriteLine(Answer);
    }
}


Measured memory_bytes: 13396
n,k=map(int, input().split())
p=list(map(int, input().split()))
ksum = sum(p[0:k])
ans = kans = ksum/2 + k*0.5
for i in range(n-k):
    ksum = ksum -p[i] +p[i+k]
    kans = ksum/2 + k*0.5
    if ans < kans:
        ans = kans
print(ans)

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

int main() {
  int n;
  scanf("%d", &n);

  int mn = n + 1, ans = 0;
  for (int i = 0; i < n; i++) {
    int p;
    scanf("%d", &p);
    
    if (p < mn) ans++;
    mn = min(mn, p);
  }

  printf("%d\n", ans);

  return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i, n, N) for(ll i=(n);i<(N);i++)
#define RREP(i, n, N) for(ll i=(N-1);i>=(n);i--)
#define CK(n, a, b) ((a)<=(n)&&(n)<(b))
#define ALL(v) (v).begin(), (v).end()
#define MCP(a, b) memcpy(b,a,sizeof(b))
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

int N;
ll A[100010];

int main() {
    cin>>N;
    REP(i,0,N){
        cin>>A[i];
    }

    sort(A, A+N);

    vector<ll> conf;

    // 小,大,小,大,...
    if(N%2 == 0){
        REP(i,0,(N-2)/2) conf.push_back(-2);
        conf.push_back(-1);
        conf.push_back(1);
        REP(i,0,(N-2)/2) conf.push_back(2);
    }else{
        REP(i,0,(N-2)/2) conf.push_back(-2);
        conf.push_back(-1);
        conf.push_back(-1);
        REP(i,0,N/2) conf.push_back(2);

    }
    ll sum1 = 0;
    REP(i,0,N){
        sum1 += A[i]*conf[i];
    }

    conf.clear();

    // 大,小,大,小,...
    if(N%2 == 0){
        REP(i,0,(N-2)/2) conf.push_back(-2);
        conf.push_back(-1);
        conf.push_back(1);
        REP(i,0,(N-2)/2) conf.push_back(2);
    }else{
        REP(i,0,N/2) conf.push_back(-2);
        conf.push_back(1);
        conf.push_back(1);
        REP(i,0,(N-2)/2) conf.push_back(2);
    }
    ll sum2 = 0;
    REP(i,0,N){
        sum2 += A[i]*conf[i];
    }

    cout<<max(sum1, sum2)<<endl;

    return 0;
}


Measured memory_bytes: 2168
# -*- coding: utf-8 -*-
import numpy as np

N = np.int64(input())
a = np.array([int(x) for x in input().split()])

min = int(1e9 + 7)
temp = int(1e9 + 7)

a_cumsum = a.cumsum()
a_sum = a.sum()

score = []

for i in range(0, N-1):
    sunuke = a_cumsum[i]
    kuma = a_sum - sunuke
    score.append(np.abs(sunuke - kuma))

print(np.array(score).min())

Measured memory_bytes: 32992
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#include<vector>
#include<map>

using namespace std;
#define endl '\n'
#define pb push_back
#define fst first
#define scd second
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define REP(i,n) for(int i = 0;i < (n);i++)
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

constexpr int MOD = 1000000007;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vector<int>> vii;

template <class T = int> T in() { T x; cin >> x; return (x); }
template <class T = int> void out(T x) { cout << (x) << endl; }

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

constexpr int MAX = 1e6;

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

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

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

ll f(ll cnt, ll N) {
	return comb(cnt + N - 1, N - 1) % MOD;
}

void solve() {

	mk_mod_comb();

	ll N, M;

	cin >> N >> M;

	ll ans = 1;

	for (ll i = 2; i <= M; i++) {
		ll cnt = 0;
		while (M % i == 0) {
			cnt++;
			M /= i;
		}
		ans *= f(cnt, N);
		ans %= MOD;
	}

	out(ans);

	return;

}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);

	solve();

	return 0;

}

Measured memory_bytes: 23680
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=200;
const int INF=1e12;
long len[size][size]={};
long dist[size][size]={};
void warshall_floyd(int n){// O(N^3)
	rep(i,0,n)rep(j,0,n){
		if(i==j) dist[i][j]=0;
		else if(len[i][j]==0) dist[i][j]=INF;
		else dist[i][j]=len[i][j];
	}rep(k,0,n)rep(i,0,n)rep(j,0,n){
		if(dist[i][j]>dist[i][k]+dist[k][j]){
			dist[i][j]=dist[i][k]+dist[k][j];
		}
	}return;
}
int main(){
	int N,M,R;cin>>N>>M>>R;
	vector<int> r(R);
	rep(i,0,R){ cin>>r[i]; r[i]--; }
	sort(r.begin(),r.end());
	int a,b;long c;
	rep(i,0,M){
		cin>>a>>b>>c;a--;b--;
		len[a][b]=c;
		len[b][a]=c;
	}warshall_floyd(N);
	long ans=INF;
	do{
		long sum=0;
		rep(i,0,R-1){
			sum+=dist[r[i]][r[i+1]];
		}ans=min(ans,sum);
	}while(next_permutation(r.begin(),r.end()));
	cout<<ans<<endl;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N,M,K;
  cin >> N >> M >> K;
  rep(n,N+1) {
    rep(m,M+1) {
      int area = n * m + (N-n) * (M-m);
      if(area == K){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
#define rep(i,n)for(int i=0;i<n;i++)
vector<int>E[100000];
int u[200000], v[200000], r[200000], ans[200000], d[100000], cnt = 1;
char b[200000], ok[100000]{ 1 };
deque<int>que;

void dfs(int u) {
	for (int v : E[u]) {
		if (d[v] > d[u] && !ok[v]) {
			ok[v] = 1; cnt++; dfs(v);
		}
	}
}
int main() {
	int n, m, q; reader(n); reader(m); reader(q);
	rep(i, m) {
		reader(u[i]); reader(v[i]);
		u[i]--; v[i]--;
		E[u[i]].emplace_back(v[i]); E[v[i]].emplace_back(u[i]);
	}
	memset(d, -1, sizeof(d));
	d[0] = 0;
	que.emplace_back(0);
	while (!que.empty()) {
		int p = que.front(); que.pop_front();
		for (int v : E[p]) {
			if (!~d[v]) {
				d[v] = d[p] + 1; que.emplace_back(v);
			}
		}
	}
	rep(i, m) {
		if (d[u[i]] > d[v[i]])swap(u[i], v[i]);
	}
	rep(i, n)E[i].clear();
	rep(i, q) {
		reader(r[i]); r[i]--;
		b[r[i]] = 1;
	}
	rep(i, m) {
		if (!b[i]) {
			if (d[v[i]] > d[u[i]]) {
				E[u[i]].emplace_back(v[i]);
			}

		}
	}
	dfs(0);
	for (int i = q - 1; i >= 0; i--) {
		ans[i] = n - cnt;
		if (d[v[r[i]]] > d[u[r[i]]] && !ok[v[r[i]]]) {
			E[u[r[i]]].emplace_back(v[r[i]]);
			if (ok[u[r[i]]]) {
				cnt++; ok[v[r[i]]] = 1;
				dfs(v[r[i]]);
			}
		}
	}
	rep(i, q)writerLn(ans[i]);
}

Measured memory_bytes: 14008
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 2000000

void maxHeap(int);
int left(int);
int right(int);
void insert(int);
int extract(void);
int parent(int);
void Heapincreace(int,int);

int A[N],c=1;
int main(){
  int i=1,kp,k;
  char C[20];

 
  
  while(1){
   
    scanf("%s",C);
    if(C[0]=='i'){
      scanf("%d",&kp);
      insert(kp);
      
    }
     
    else if(C[0]=='e'&&C[1]=='x'){
    k=extract();
    printf("%d\n",k);
    }
    else
      break;
    
  }
  
  return 0;
}


void maxHeap(int i){
  int l,v,r,largest;

  l=left(i);
  r=right(i);

  if(l<=c&&A[l]>A[i])
    largest=l;
  else
    largest=i;
  if(r<=c&&A[r]>A[largest])
    largest=r;

  if(largest!=i){
    v=A[i];
    A[i]=A[largest];
    A[largest]=v;
    maxHeap(largest);
  }

}
void insert(int i){
  c++;
  A[c]=-270000000;
  Heapincreace(c,i);
}

int extract(){
  int max;
  if(c<1){
    printf("heap underflow");
    exit(8);
  }
  max=A[1];
  A[1]=A[c];
  c--;
  maxHeap(1);
  return max;
}

void Heapincreace(int a,int i){
  int k;
  if(i<A[a]){
    printf("new key is smaller than current key");
    exit(8);
  }
  A[a]=i;
  while(a>1&&A[parent(a)]<A[a]){
    k=A[a];
    A[a]=A[parent(a)];
    A[parent(a)]=k;
    a=parent(a);
  }
}

int parent(int i){
  return i/2;
}

int left(int i){
  return 2*i;
}

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

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

#ifndef ONLINE_JUDGE
    #define gc getchar
    #define pc putchar
#else
    #define gc getchar_unlocked
    #define pc putchar_unlocked
#endif

using namespace std;

#define vi vector<int>
#define si set<int>
#define vs vector<string>
#define pii pair<int,int>
#define vpi vector<pii>
#define pri priority_queue<int>
#define rev_pri priority_queue<int,vector<int>,greater<int> >
#define mpi map<int,int>
#define i64 long long int
#define endl '\n'
#define pi acos(-1)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf INT_MAX/2
#define infll LLONG_MAX/3
#define For(i,n) for(int i=0;i<n;i++)
#define Fre(i,a,b) for(int i = a; i < b; i++)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pfn(n) printf("%d\n", n)
#define pfs(n) printf("%d ", n)
#define eps 1e-8
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define READ freopen("in.txt", "r", stdin)
#define WRITE freopen("out.txt", "w", stdout)
#define sz size()
#define dbg(i) printf("yo %d\n", i)
#define foreach(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define sqr(a) (a) * (a)
#define clr clear()
#define CASE(a) printf("Case %d: ",a)

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


//i64 gcd(i64 a,i64 b){if(!b)return a;return gcd(b,a%b);}

//inline void fastRead(int *a){register char c=0;while(c<33)c=gc();*a=0;while(c>33){*a=*a*10+c-'0';c=gc();}}

//inline void fastWrite(int a){char snum[20];int i=0;do{snum[i++]=a%10+48;a=a/10;}while(a!=0);i=i-1;while(i>=0)pc(snum[i--]);pc('\n');}

//i64 bigmod(i64 num,i64 n){if(n==0)return 1;i64 x=bigmod(num,n/2);x=x*x%mod;if(n%2==1)x=x*num%mod;return x;}

//i64 modinverse(i64 num){return bigmod(num,mod-2)%mod;}

//i64 po(i64 a,i64 b){i64 ans=1;while(b--)ans *= a;return ans;}

//i64 ncr(i64 n,i64 r){if(n==r)return 1;if(r==1)return n;if(dp[n][r]!=-1)return dp[n][r];return dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);}


// bit manipulations

//bool checkbit(int mask,int bit){return mask & (1<<bit);}

//int setbit(int mask,int bit){ return mask  (1<<bit) ; }

//int clearbit(int mask,int bit){return mask & ~(1<<bit);}

//int togglebit(int mask,int bit){return mask ^ (1<<bit);}


vi v;
int main()
{


        int n,k,pos,inp;
        sff(n,k);


        For(i,n)
        {
                sf(inp);
                v.pb(inp);
        }


        if(k>=n)
        {
                cout << 1 << endl;
                return 0;
        }
        int ans = 0;

        for(int i = 0 ; ;i += k-1)
        {
                if (i>=n-1)
                        break;
                ans++;
        }


        cout << ans << endl;








        return 0;
}




Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair
#define vecin1(n) vector<int> vec1(n); rep(i,n) cin >> vec1.at(i)
#define vecin2(n) vector<int> vec2(n); rep(i,n) cin >> vec2.at(i)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;


int main() {

int ans,A,B = 0;
cin >> A >> B;
if(A == B) //A==Bのときは，A,Bを抽出するのがコインの枚数の最大値
ans = 2*A;
else //A==Bでないときは，大きい方を2連続で選ぶのがコインの枚数の最大値
ans = 2*max(A,B)-1;


  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>

int main()
{
	int h,w,t;
	bool found = false;
	std::cin >> h >> w >> t;
	for(int lx=0;lx<=h;lx++)
	{
		for(int ly=0;ly<=w;ly++)
		{
			if((lx*(w-ly)+(h-lx)*ly) == t)
			{
				found = true;
				goto end;
			}
		}
	}
end:
	std::cout << (found?"Yes":"No") << std::endl;
}


Measured memory_bytes: 888
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define pr pair<int,int>
#define endl "\n"
#define MOD 1000000007 // 10^9 + 7
#define sz(x) (int)(x).size()
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define all(c) (c).begin(), (c).end()

#define FOR(i,b) for (int i = 0; i < (b); i++)
#define FORR(i,a,b) for (int i = a; i < (b); i++)
#define FORB(i,b) for (int i = (b); i >= (0); i--)
#define FORRB(i,a,b) for (int i = (a);i>= (b); i--)

using namespace std;

int n,w,weight[110],value[110];

ll dp[100010];

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

    //freopen("addin.txt","r",stdin);
    //freopen("addout.txt","w",stdout);
    cin >> n >> w;
    for(int i = 0;i < n;i++) {
        cin >> weight[i] >> value[i];
    }
    for(int i=0;i<n;i++){
        for(int j = w;j >= 0 ;j--){
            if((j+weight[i]) <= w) dp[j+weight[i]] = max(dp[j+weight[i]],dp[j]+value[i]);
        }
    }
    ll max1 = 0;
    for(int i=0;i<=w;i++) max1 = max(max1,dp[i]);
    cout<<max1<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[100005], b[100005], c[100005];
ll dp[1005][100005];
int main() {
	int n, W;
	cin >> n >> W;
	ll w[105], v[105];
	for (int i = 0; i < n; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i <= W; i++) {
		dp[0][i] = 0;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= W; j++) {
			if (j >= w[i]) {
				dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
			}
			else {
				dp[i + 1][j] = dp[i][j];
			}
		}
	}
	cout << dp[n][W] << endl;
	return 0;
}

Measured memory_bytes: 80128
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;
#define INF 10000000000000
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for(ll i = 1; i < (ll)(n); i++)
#define repN_1(i, n) for(ll i = 0; i < (ll)(n - 1); i++)
#define repM(i, n) for(ll i = (ll)(n - 1); i >= 0; 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 main()
{
	ll n, c, k, ans;
	cin >> n >> c >> k;
	ans = 0;

	vector<ll> t(n);

	rep(i, n)
		cin >> t[i];

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

	ll f, r; // f:現在のバスに乗る最初の乗客の到着時間，r:バスに現在何人乗っているか
	f = r = 0;
	rep(i, n)
	{
		r++;
		// バスに乗客がいないとき
		if (f == 0)
		{
			f = t[i];
			ans++;
		}
		// 捌く対象の客が，バスの最初の乗客が乗ってからkより大きい時間たってから到着するとき
		if (t[i] - f > k)
		{
			r = 1;
			f = t[i];
			ans++;
		}
		// バスの定員が埋まったとき
		else if (r == c)
		{
			f = 0;
			r = 0;
		}

	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
package main

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

func main() {
	var ans = make([]int, 3)
	var sc = bufio.NewScanner(os.Stdin)
	sc.Scan()
	ABC   := strings.Split(sc.Text(), " ")
	A, _  := strconv.Atoi(ABC[0])
	B, _  := strconv.Atoi(ABC[1])
	C, _  := strconv.Atoi(ABC[2])
	sc.Scan()
	K, _  := strconv.Atoi(sc.Text())
	
	ans[0] = toDouble(A, K) + B + C
	ans[1] = A + toDouble(B, K) + C
	ans[2] = A + B + toDouble(C, K)
	
	fmt.Println(max(ans))

}

func toDouble(N int, K int) int {
	for i := 0; i < K; i++ {
		N *= 2
	}
	return N
}

func max(a []int) int {
	max := a[0]
	for _, i := range a {
		if i > max {
			max = i
		}
	}

	return max
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
double a[1005];
int main(){
	int n;
	while(1){
		double s=0;
		double res=0;
		cin>>n;if(n==0)break;
		for(int i=0;i<n;i++)cin>>a[i],s+=a[i];
		for(int i=0;i<n;i++)res+=a[i]*a[i];
		res=res-s*s/n;
		res=res/n;
		printf("%.10f\n",sqrt(res));
	}
	return 0;
}


Measured memory_bytes: 3204
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

int main() {
    int N, M;
    cin >> N >> M;
    vector<ll> card(N);
    for (int i = 0; i < N; i++) {
        cin >> card[i];
    }
    vector<pair<ll, ll>> change(M);
    for (int i = 0; i < M; i++) {
        cin >> change[i].second >> change[i].first;
    }

    sort(card.begin(), card.end());
    sort(change.begin(), change.end());

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (change.empty() || change.back().first <= card[i]) {
            ans += card[i];
        } else {
            ans += change.back().first;
            change.back().second--;
            if (change.back().second == 0) {
                change.pop_back();
            }
        }
    }
    cout << ans << endl;
    return 0;
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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; }

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

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

  cout << (s[s.size()-1]=='s' ? s + "es" : s + "s" ) << endl;
}



Measured memory_bytes: 3632
def insert_sort(A):
    array = A[:]
    for i in range(1, len(array)):
        print(' '.join(array))
        v = array[i]
        j = i - 1

        while j >= 0 and int(array[j]) > int(v):
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = v
    return array

_, A = input(), input().split()
print(' '.join(insert_sort(A)))


Measured memory_bytes: 5596
import java.util.Scanner;

public class Main {

	public static Scanner scanner = new Scanner(System.in);

	public static void main(String[] args) {

		int counter = 0;
		int a = input();
		int b = input();
		int c = input();

		for (int i = a; i <= b; i++) {

			if (c % i == 0) {

				counter++;

			}
		}

		System.out.println(counter);

		close();

	}

	public static int input() {

		return scanner.nextInt();

	}

	public static void close() {

		if (scanner != null) {

			scanner.close();

		}
	}
}

Measured memory_bytes: 26248
#include <stdio.h>
 
int main(){
    int N , ans = 0,S ,y;
    scanf("%d" ,&N);
    while(N--){
	scanf("%d" ,&S);
 
	int flg = 0;
	for(y = 1 ; 2*y*y <= S ; y++){
	    if((S - y) % (2*y + 1) == 0){
		flg = 1;
		break;
	    }
	}
	if(!flg){
	    ans++;
	}
    }
    printf("%d\n" ,ans);
    return 0;
}

Measured memory_bytes: 2692
#include "bits/stdc++.h"
using namespace std;

long InsertionSort(vector<int>& A, int n, int g) {
  long cnt = 0;
  for (int i = g; i < n; ++i) {
    int v = A[i];
    int j = i - g;
    while (j >= 0 && A[j] > v) {
      A[j + g] = A[j];
      j = j - g;
      ++cnt;
    }
    A[j + g] = v;
  }
  return cnt;
}

void ShellSort(vector<int>& A, int n) {
  vector<int> G; // = {1, 4, 13, 40, 121...}
  //g_n+1 = 3g_n + 1?????°????????¨????????¨O(N^1.25)??¨???????????¨????????¶????????£????????¬???????????????
  for (int i = 1; i <= n; i = 3 * i + 1) {
    G.push_back(i);
  }
  cout << G.size() << endl;  //output m
  //?????????????????????????????\?????????
  long cnt = 0;
  for (auto itr = G.crbegin(); itr != G.crend(); ++itr) {
    if (itr != G.crbegin()) cout << " "; // output[13 4 1]
    cout << *itr;
    cnt += InsertionSort(A, n, *itr);
  }
  cout << endl;
  cout << cnt << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n; //input
  vector<int> A(n);
  for (auto& a : A)
    cin >> a; //input
  ShellSort(A, n);
  for (auto& a : A)
    cout << a << endl;  //output
  //system("pause");
}

Measured memory_bytes: 6756
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (1E9+7)
#define PI 3.1415926535897932384

std::ostream &operator<<(std::ostream &out, const vector<int> &tgt)
{
	string s;
	for (int i = 0; i<tgt.size(); i++) {
		s += (to_string(tgt[i]) + ((i != tgt.size() - 1) ? " " : ""));
	}
	out << s;
	return out;
}

int main() {
	ll a, b, d;
	cin >> a >> b >> d;
	ll ans = (b/d+1-(a==0?0:(a-1)/d+1));
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define swap(a, b, type) { type _tmp = a; a = b; b = _tmp; }
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int N, X, f = 0;
	bool ans = false;

	cin >> N;
	X = N;

	while (X > 0) {
		f += X % 10;
		X /= 10;
	}

	if (N % f == 0) ans = true;

	cout << (ans ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N,K;cin>>N>>K;
	int A[N];vector<int> backet(N,0);
	int count=0;
	for(int i=0;i<N;i++){
		cin>>A[i];
		if(backet[A[i]-1]==0){
			count++;
		}backet[A[i]-1]++;
	}sort(backet.begin(),backet.end());
	if(count<=K){
		cout<<0<<endl;
		return 0;
	}else{
		count=count-K;
	}int result=0;int a=0,b=0;
    while(a<count&&b<N){
		if(backet[b]!=0){
		    result+=backet[b];
		    a++;
		}b++;
	}cout<<result<<endl;
}

Measured memory_bytes: 1792
N = int(input())
S = list(input())

def E_W():
    score = []
    s = 0
    
    for i in range(N):
        if (S[i] == 'W'):
            s -= 1
        else:
            s += 1
        score.append(s)
    
    max_index = score.index(max(score))
    
    cnt = S[:max_index].count('W') + S[max_index + 1 :].count('E')
    
    
    return (cnt)

ans = E_W()
print(ans)

Measured memory_bytes: 19832
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <utility>
using namespace std;
using ll = long long int;
using pa = pair<int, int>;

int main() {
	int N;
	cin >> N;
	vector<int> A(N), B(N);
	vector<pair<pa,int>> C(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		C[i] = make_pair(make_pair(-A[i] - B[i],A[i]),i);
	}
	sort(C.begin(), C.end());
	ll sum = 0;

	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) {
			sum += A[C[i].second];
		}
		else {
			sum -= B[C[i].second];
		}
	}

	cout << sum;
	return 0;
}

Measured memory_bytes: 2176