akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define int int64_t
#define pcnt __builtin_popcount
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define vec vector<int>
#define mat vector<vector<int>> //mat データ名(縦,vec(横));
#define F first
#define S second
int INF = 1000000000000000001; //10^18+1
int MOD = 1000000007; //10^9+7
//cout << fixed << setprecision(15); (小数点以下表示)

signed main () {
  int N,M,X,ans=INF,score=0;
  cin >> N >> M >> X;
  vec C(N),S(M);
  mat A(N,vec(M));
  for(int i=0;i<N;i++){
    cin >> C.at(i);
    for(int j=0;j<M;j++){
      cin >> A.at(i).at(j);
    }
  }
  for(int i=0;i<(1<<N);i++){
    score=0;
    vector<bool>a(M);
    int cnt=0;
    vec S(M);
    for(int j=0;j<N;j++){
      if(i&(1<<j)){
        score+=C.at(j);
        for(int k=0;k<M;k++){
          S.at(k)+=A.at(j).at(k);
          if(S.at(k)>=X&&!a.at(k)){
            a.at(k)=true;
            cnt++;
          }
        }
      }
    }
    if(cnt==M)ans=min(ans,score);
  }
  if(ans==INF)ans=-1;
  cout << ans << endl;
}

Measured memory_bytes: 3608
package main

import "fmt"

func main() {
	var N, K int
	fmt.Scan(&N, &K)
	A := make(map[int]int)
	for i := 0; i < N; i++ {
		var v int
		fmt.Scan(&v)
		A[i] = v
	}

	num := make(map[int]int, 0)
	tele := 0
	k := 0
	var rep int

	for {
		if num[tele] != 0 {
			rep = k - num[tele]
			break
		}
		num[tele] = k
		tele = A[tele] - 1
		k++
	}

	ans := 0
	if K <= num[tele] {
		for l := 0; l < K; l++ {
			ans = A[ans] - 1
		}
	} else {
		K = (K-num[tele])%rep + num[tele]
		for l := 0; l < K; l++ {
			ans = A[ans] - 1
		}
	}
	fmt.Println(ans + 1)
}


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


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())


//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

	vector<vector<int>>tb(n+1, vector<int>(3));

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

	//dp[i日まで選んで][最後に選んだのがa,b,c]のときの幸福度の最大値

	vector<vector<int>> dp(n + 1, vector<int>(3, -1));

	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {

				if (j == k)continue;

				dp[i][j] = max(dp[i][j], dp[i - 1][k] + tb[i][j]);
			}
		}
	}

	LL ans = -1;
	for (int j = 0; j < 3; j++) {
		ans = max(ans, (LL)dp[n][j]);
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 11136
#include<stdio.h>

int max(int len,int *nums) {
	int i,_max = nums[0];
	int *count =nums;
	for(i = 1; i < len; i++) {
		if(nums[i] > _max) {
			_max = nums[i];
			count = &nums[i];
		}
	}
	return _max;
}
int main() {
    int n,sum = 0;
    scanf("%d",&n);
    int P[n];
    for(int j = 0; j < n; j++) {
    	scanf("%d",&P[j]);
    	sum += P[j];
    }
    sum-=max(n,P)/2;
    printf("%d",sum);

	return 0;
}

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

int main() {
	int V[20];
	int C[20];
	int x = 0;
	cin >> x;
	for (int i = 0; i < x; i++) {
		cin >> V[i];
	}
	for (int i = 0; i < x; i++) {
		cin >> C[i];
	}
	int GO = 0;
	for (int i = 0; i < x; i++) {
		if (V[i] > C[i]) {
			GO += V[i] - C[i];
		}
	}
	cout << GO << endl;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a=[list(map(int,list(input().replace('.','0').replace('#','1')))) for i in range(n)]
b=[list(map(int,list(input().replace('.','0').replace('#','1')))) for i in range(m)]
ans='No'
for i in range(n-m+1):
  for j in range(n-m+1):
    c=[a[k][j:j+m] for k in range(i,i+m)]
    if c==b:
      ans='Yes'
      break
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
main(){
int s[9000],n,m,t,f,i;
while(scanf("%d%d",&n,&m),i=t=f=1,n){
	while(i<=n+m){
		if(scanf("%d",&s[i]),i>n)if(t+=s[t+=s[i]],t>=n&f==1)
				printf("%d\n",i-n,f=0);
				i++;
	}
}
	
}

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

int main() {
  int N, K, a, sum;
  cin >> N >> K;
  sum = 0;
  
  for (int i=0; i<N; i++){
    int x;
    cin >> x;
    
    if (x <= K-x){
      sum += 2*x;
    }
    else{
      sum += 2*(K-x);
    }
  }
  
  cout << sum << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr0=limii()

arr=Counter(arr0)

ai=list(arr.items())
ai.sort()
if n%2==0:
    cnt=0
    for p,i in enumerate(range(1,n,2)):

        if ai[p][0]==i and ai[p][1]==2:
            cnt+=1
    if cnt==n//2:
        print((2**(n//2))%mod)
    else:
        print(0)
else:
    cnt=0
    for p,i in enumerate(range(0,n,2)):
        if p==0:
            if ai[p][0]==i and ai[p][1]==1:
                cnt+=1
        else:        
            if ai[p][0]==i and ai[p][1]==2:
                cnt+=1
    if (n+1)//2==cnt:
        print((2**(cnt-1))%mod)
    else:
        print(0)

Measured memory_bytes: 82168
n = int(input())
c = list(input())
w = 0
r = c.count("R")
ans = r
for i in range(n) :
    if c[i] == "W" :
        w += 1
    else :
        r -= 1
    if ans > max(w,r) :
        ans = max(w,r)

print(ans)


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

int main() {
	long long N, K; cin >> K >> N;
	vector<long long> A(N);
	long long max = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	max = K - A[N - 1] + A[0];
	for (int i = 0; i < N-1; i++)
	{
		if (max < A[i + 1] - A[i])max = A[i + 1] - A[i];
	}
	cout << K - max << endl;
}

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from time import time
from random import randint
from copy import deepcopy

start_time = time()

def calcScore(t, s, c):
    scores = [0]*26
    lasts = [0]*26
    for i in range(1, len(t)):
        scores[t[i]] += s[i][t[i]]
        dif = i - lasts[t[i]]
        scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
        lasts[t[i]] = i
    for i in range(26):
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2
    return scores

def update(socre, day, t, q):
    p = t[day]
    t[day] = q
    scores[p] = 0
    scores[q] = 0
    lasts = [0]*26
    for i in range(1, len(t)):
        if t[i] == p or t[i] == q:
            scores[t[i]] += s[i][t[i]]
            dif = i - lasts[t[i]]
            scores[t[i]] -= c[t[i]] * dif * (dif-1) // 2
            lasts[t[i]] = i
    for i in [p, q]:
        dif = len(t) - lasts[i]
        scores[i] -= c[i] * dif * (dif-1) // 2

def greedy(c, s):
    day_lim = len(s)
    socres = [0]*26
    t = [0]*day_lim
    lasts = [0]*26
    for i in range(1, day_lim):
        pls = [v for v in socres]
        mns = [v for v in socres]
        for j in range(26):
            pls[j] += s[i][j]
            mns[j] -= c[j] * (i - lasts[j])
        sum_mns = sum(mns)
        pt = sum_mns - mns[0] + pls[0]
        idx = 0
        for j in range(1, 26):
            tmp = sum_mns - mns[j] + pls[j]
            if pt < tmp:
                pt = tmp
                idx = j
        t[i] = idx
        lasts[idx] = i
        for j in range(26):
            if j == idx:
                socres[j] = pls[j]
            else:
                socres[j] = mns[j]
    return socres, t

D = int(input())
c = list(map(int, input().split()))
s = [[0]*26 for _ in range(D+1)]
for i in range(1, D+1):
    s[i] = list(map(int, input().split()))

scores, t = greedy(c, s)
sum_score = sum(scores)

while time() - start_time < 1.75:
    day = randint(1, D)
    q = randint(0, 25)
    if q == t[day]:
        continue
    tmp_scores = deepcopy(scores)
    tmp_t = deepcopy(t)
    update(tmp_scores, day, tmp_t, q)
    sum_tmp_score = sum(tmp_scores)
    if sum_score < sum_tmp_score:
        sum_score = sum_tmp_score
        t = tmp_t
        scores = tmp_scores

for v in t[1:]:
    print(v+1)

Measured memory_bytes: 91720
//   <<In The Name Of God>>
// PTD
/*
ID: alimora2
LANG: C++11
TASK: PROB
*/
#include <bits/stdc++.h>

#define sqr(A) (A) * (A)
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 1, mod = 1e9 + 7;
int r[maxn];

ll calc(int n) {
	ll res = 1;
	for (int i = 0; i < n; i++) {
		res *= 2;
		res %= mod;
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		r[a]++;
		if ((n % 2 == 0 && a == 0) || r[a] > 2 || (n % 2 == 1 && r[0] > 1))
			return cout << 0 << endl, 0;
	}
	cout << calc(n / 2) << endl;
}

Measured memory_bytes: 640
import sys
  
r = []
for string in sys.stdin:
    i = 0
    s = ""
    sin = string.strip()
    while i < len(sin):
        if sin[i] == '@':
            s += sin[i+2] * int(sin[i+1])
            i = i+3
        else:
            s += sin[i]
            i += 1
    r.append(s)

print(*r, sep='\n')


Measured memory_bytes: 5608
// Copyright: lzt
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<long long,long long> pll;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k)  for(register int i=(int)(j);i<=(int)(k);i++)
#define rrep(i,j,k) for(register int i=(int)(j);i>=(int)(k);i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)

ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}

int a[] = {0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73};
ll w[15][15];

void work() {
	int n = read();
	w[1][2] = w[2][1] = 1;
	rep(i, 3, n) {
		ll s = 0;
		int p[15];
		rep(x, 1, i - 1) p[x] = x;
		do {
			ll nw = 0;
			rep(x, 1, i - 2) nw += w[p[x]][p[x + 1]];
			s = max(s, nw);
		} while (next_permutation(p + 1, p + i));
		s++;
		rep(x, 1, i - 1) w[x][i] = w[i][x] = s * a[x];
	}
	rep(i, 1, n) {
		rep(j, 1, n) printf("%lld ", w[i][j]);
		puts("");
	}
}

int main(){
	#ifdef LZT
		freopen("in","r",stdin);
	#endif

	work();

	#ifdef LZT
		Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
	#endif
}


Measured memory_bytes: 256
-- AtCoder My Practice
-- author: Leonardone @ NEETSDKASU
 
-- 解説読後
-- http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf

import qualified Data.ByteString.Char8 as C
import Data.Array (listArray, accumArray, (!))
 
main = print . solve .map red . C.words =<< C.getContents
    where
        red x = case C.readInteger x of Just v -> fst v

solve (n:x:a) = ans where
    sm = sum a
    ans = f n sm a
    f 1 r _  = r
    f c r ar = f (c - 1) r2 ar2 where
        ar2 =zipWith min a $ [last ar] ++ ar
        r2 = minimum [r, (n - c + 1) * x + sum ar2]


Measured memory_bytes: 3452
/*
   Author: Shivam Shukla
*/
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pair<ll,ll> > vpll;
 
const int MOD=1e9+7;
const int MAX=1e5+5;
const double PI= acos(-1.0);
const long double EPS=1e-10;
const int64_t INF=1e18+10;
 
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0)
#define trace(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vi vector<int>
#define vl vector<ll>
#define vs vector<str>
#define vc(x) vector<x>
#define mapll map<ll,ll>
#define mapib map<int,bool>
#define mapiv map<int,vector>
#define mapsi map<string,int>
#define rep(i,j,k) for(ll i=j;i<k;i++)
#define down(i,j,k) for(ll i=j;i>=k;i--)
#define repa(i,n) for(ll i=0;i<n;i++)
#define dowa(i,n) for(ll i=n;i>=0;i--)
#define reps(i,j,k,s) for(ll i=j;i<k;i+=s)
#define downs(i,j,k,s) for(ll i=j;i>=k;i-=s)
#define trv(i,x) for(auto i:x)
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define str string 
#define dub double
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vl,greater<ll> >
 
template<typename t> t lcm(t a, t b) {return (a*b)/__gcd(a,b);}
template<typename t> t gcd(t a, t b) {return __gcd(a,b);}
template<typename t> t mul_mod(t a, t b, t m){t res=((a%m)*(b%m)%m); return res;}
template<typename t> t add_mod(t a, t b, t m){t res=((a%m)+(b%m))%m; return res;}
template<typename t> t pow_mod(t a,t b,t m) {t res=1;while(b){if(b&1) res=mul_mod(res,a,m);a=mul_mod(a,a,m), b>>=1;} return res%m;}
template<typename t> vc(t) num_vec(t num) {t res; while (num) res.pb(num%10), num/=10; return res;}
template<typename t> t vec_num(t vec) {t res=0; ll mul=1; repa(i,sz(vec)) res=vec[i]*mul, mul*=10; return res;}
 
bool chr(vc(vl) mat, int r) {
    repa(i, 3)
       if (mat[r][i] != -1)
       	  return false;
    return true;   	
}

bool chc(vc(vl) mat, int c) {
    repa(i, 3)
       if (mat[i][c] != -1)
       	  return false;
    return true;   	
}

bool chld(vc(vl) mat){
    repa(i, 3)
       if(mat[i][i] != -1)
       	   return false;
    return true;   	
}

bool chrd(vc(vl) mat) {
    repa(i, 3)
       if (mat[i][2 - i] != -1)
       	   return false;
    return true;   	
}

int32_t main(int argc,char** argv){
	fastio();
	auto tstart= clock();
 


    vc(vl) mat(3, vl(3));

    repa(i,3)
      repa(j, 3)
         cin >> mat[i][j];

    int n; cin >> n;

    while (n--) {
    	int b; cin >> b;

    	repa(i,3)
    	   repa(j,3)
    	     if (mat[i][j] == b)
    		    mat[i][j] = -1;
    }   
    
    repa(r,3) {
    	if (chr(mat,r))
    		 return cout << "Yes" << endl, 0;   		
    }

    repa(c, 3) {
    	if (chc(mat, c))
    		 return cout << "Yes" << endl, 0;
    }

    if (chld(mat) || chrd(mat))
    	 return cout << "Yes" << endl , 0;
   

    cout << "No" << endl;
    	
    cerr<<setprecision(2)<<fixed<<"Time elapsed: "<<(double)(clock() - tstart)/CLOCKS_PER_SEC<<endl; 
    return 0; 
}

Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	k := getNextInt(scanner)

	ans := 0
	for i := k + 1; i <= n; i++ {
		ans += (n / i) * (i - k)
		if n%i >= k {
			ans += n%i - k + 1
			if k == 0 {
				ans--
			}
		}
	}

	fmt.Fprintln(writer, ans)
	writer.Flush()
}


Measured memory_bytes: 640
#include <stdio.h>
int main (void){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    int hi1 = a+b;
    int hi2 = a+c;
    int hi3 = b+c;
    if (hi1>hi2){
        if (hi2 > hi3){
            printf("%d\n",hi3);
        }else{
            printf("%d\n",hi2);
        }
    }else{
        if(hi1 > hi3){
            printf("%d\n",hi3);
        }else{
            printf("%d\n",hi1);
        }
    }
    return 0;
}


Measured memory_bytes: 128
using System;
using System.Linq;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using static program.Input;
using static program.MyMath;
using static System.Console;

namespace program {
  class Program {
    static string Alp = "abcdefghijklmnopqrstuvwxyz";
    static void Main()
    {
      var nq = ScanIntArray();
      var n = nq[0];
      var q = nq[1];
      var s = ScanStr();
      
      int[] len = new int[n];
      len[0] = 0;
      for(int i=1; i<n; i++){
        if(s[i-1]=='A' && s[i]=='C') len[i] = len[i-1]+1;
        else len[i] = len[i-1];
      }
      //
      
      for(int i=0; i<q; i++){
        var qi = ScanIntArray();
        WriteLine($"{len[qi[1]-1] - len[qi[0]-1]}");
      }
    }
  }
  
  static class Input {
    static public int ScanInt() { return int.Parse(Console.ReadLine()); }
    static public uint ScanUint() { return uint.Parse(Console.ReadLine()); }
    static public double ScanDouble() { return double.Parse(Console.ReadLine()); }
    static public long ScanLong() { return long.Parse(Console.ReadLine()); }
    static public ulong ScanUlong() { return ulong.Parse(Console.ReadLine()); }
    static public int[] ScanIntArray() { return Console.ReadLine().Split().Select(x => int.Parse(x)).ToArray(); }
    static public uint[] ScanUintArray() { return Console.ReadLine().Split().Select(x => uint.Parse(x)).ToArray(); }
    static public double[] ScanDoubleArray() { return Console.ReadLine().Split().Select(x => double.Parse(x)).ToArray(); }
    static public long[] ScanLongArray() { return Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray(); }
    static public ulong[] ScanUlongArray() { return Console.ReadLine().Split().Select(x => ulong.Parse(x)).ToArray(); }

    static public string ScanStr() { return Console.ReadLine(); }
    static public string[] ScanStrArray() { return ScanStr().Split(); }
    static public string RegaxReplace(this string arg1, string pattern, string replacement)
    {
      return Regex.Replace(arg1, pattern, replacement);
    }
  }
  
  static class MyMath {
    public static int GCD(int a, int b) {
        Func<int, int, int> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static long GCD(long a, long b) {
        Func<long, long, long> gcd = null;
        gcd = (x, y) => y == 0 ? x : gcd(y, x % y);
        return a > b ? gcd(a, b) : gcd(b, a);
    }
    public static ulong extGCD(ulong a, ulong b, ref ulong x, ref ulong y) {
      if(b==0) {
        x=1; 
        y=0;
        return a;
      }
      var d = extGCD(b, a%b, ref y, ref x);
      y -= a/b *x;
      return d;
    }
    public static int LCM(int a, int b) { return a * b / GCD(a, b); }
    public static long LCM(long a, long b) { return a * b / GCD(a, b); }
  }
}


Measured memory_bytes: 18612
N=int(input())
x=[0]
y=[0]
t=[0]

flag=1
for i in range(1,N+1):
  t_tmp,x_tmp,y_tmp=map(int,input().split())
  t.append(t_tmp)
  x.append(x_tmp)
  y.append(y_tmp)
  time=abs(t[i-1]-t[i])
  d=abs(x[i-1]-x[i])+abs(y[i-1]-y[i])
  if d>time or (d%2)!=(time%2):
    print("No")
    flag=0
    break
    
if flag==1:
  print("Yes")

Measured memory_bytes: 11764
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  map<int,int>M;
  for(int i=1;i<=N;i++)
    M[i]=0;
  for(int i=0;i<N-1;i++){
  int x;
    cin>>x;
    M.at(x)++;
  }for(auto p:M){
   auto k=p.first;
    auto v=p.second;
    cout<<M.at(k)<<endl;
  
  }
   return 0;
}

Measured memory_bytes: 13000
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 200005
#define P 998244353
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, cnt, head[MAXN], ans[MAXN], mv[MAXN];

map<int, int> mp[MAXN];

struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

int cal(int x, int fa, int val)
{
    if(mp[x].count(val)) return mp[x][val];
    int temp=0;
    for(rint i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to>=val) continue;
        temp+=cal(to, x, val)+1;
    }
    mp[x][val]=temp;
    return temp;
}

void dfs(int x, int fa)
{
    for(rint i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        ans[to]=ans[x];
        mv[to]=max(mv[x], x);
        if(to>mv[x]) ans[to]+=cal(to, x, mv[to])+1;
        else ans[to]+=cal(to, x, mv[to])-cal(to, x, mv[x]);
        dfs(to, x);
    }
}

int main()
{
    scanf("%d", &n);
    for(rint i=1, x, y; i<n; ++i)
    {
        scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    dfs(1, 0);
    for(rint i=2; i<=n; ++i) printf("%d ", ans[i]);
    return 0;
}

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

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    int odd = 0;
    for(auto& x : a){
        cin >> x;
        x = x & 1;
        odd += x;
    }
    int even = n - odd;
    if(odd == n || even == n){
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    ans += even - 1;
    even = 1;
    while(even && odd){
        if(even == 2){
            ++ans;
            even = 1;
        }
        else if(odd >= 2){
            ++ans;
            odd -= 2;
            even += 1;
        }
        else if(odd == 1 && even == 1){
            ++ans;
            --even;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 3620
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(input())
S = input()

if len(S) <= K:
    print(S)
else:
    print(S[:K] + '...')


Measured memory_bytes: 9408
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se seoncd
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=1005;
const char m3[3][4]={
	"..a",
	"..a",
	"bb."
};
const char m5[5][6]={
	"abbcc",
	"add.e",
	"f..ge",
	"f..gh",
	"iijjh"
};
const char m7[7][8]={
	"..a..bc",
	"..a..bc",
	"ddeff..",
	"..e.ghh",
	"..iigjj",
	"kk.lm..",
	"nn.lm.."
};
char ans[N][N];
int n;

void R(int x,int y){
	char c='a'+(x*3+y)%9;
	ans[x][y]=ans[x][y+1]=c;
}
void D(int x,int y){
	char c='a'+(x*3+y)%9;
	ans[x][y]=ans[x+1][y]=c;
}

int solve(int b,int n){
	if(n<=2) return 0;
	if(n%2==0){
		REP(i,n/2){
			int j=(i+1)%(n/2);
			R(b+1+i*2,b+1+i*2);
			R(b+1+i*2+1,b+1+i*2);
			D(b+1+i*2,b+1+j*2);
			D(b+1+i*2,b+1+j*2+1);
		}
		return 1;
	}
	if(n==3){
		REP(i,3) REP(j,3)
			ans[b+1+i][b+1+j]=m3[i][j];
		return 1;
	}
	if(n==5){
		REP(i,5) REP(j,5)
			ans[b+1+i][b+1+j]=m5[i][j];
		return 1;
	}
	if(n==7){
		REP(i,7) REP(j,7)
			ans[b+1+i][b+1+j]=m7[i][j];
		return 1;
	}
	solve(b,n-5),solve(b+n-5,5);
	return 1;
}

int main(){
	read(n);
	rep(i,1,n) rep(j,1,n) ans[i][j]='.';
	if(!solve(0,n)){
		puts("-1");
		return 0;
	}
	rep(i,1,n) puts(ans[i]+1);
	return 0;
}

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

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

int main(){
    long long H, W;
    cin >> H >> W;
    long long sum = 0;

    for(long long i = 1; i <= H; i++){
        
        if(W == 1 || H == 1){
            sum = 1;
            break;
        }else if(W % 2 == 0){
            sum += W / 2;
        }else{
            if(i % 2 == 0){
                sum += W / 2;
            }else{
                sum += W / 2 + 1;
            }
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  ll n, k; cin >> n >> k;
  ll ans = 0;
  for (ll i = k; i <= n+1; i++) {
    ll left = (0+i-1)*i/2;
    ll right = ((n-(i-1))+n)*i/2;
    ans += right-left+1;
  }
  COUT(ans % MOD);
  return 0;
}

Measured memory_bytes: 3632
//Author: kaiyu
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
#define sz(x) ((long long)(x).size())
#define all(x)  x.begin(),x.end()
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<int,int>
#define tt ll t;cin >> t;while(t--)
#define int3(x,y,z) ll x,y,z;cin >> x >> y >> z;
#define int2(x,y) ll x,y;cin >> x >>y;
#define int1(x) ll x;cin>>x;
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
ll power(ll a,ll b,ll m=mod){ ll ans=1; a=a%m;  while(b>0) {  if(b&1)  ans=(1ll*a*ans)%m; b>>=1;a=(1ll*a*a)%m;}return ans;}

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

bool cmp(pair<string,int>p1,pair<string,int>p2) {
    return p1.ss > p2.ss;
}

const int MAXN = 5 * 100000 + 10;

//#define int long long
vector<ll> dp(MAXN,INT_MAX);
void path(int n,int * h,int k) {
    for (int i = 0; i < n; ++i) {
        if(i == 0) {
            dp[i] = 0;
            int x = dp[i];
        }
        else if(i == 1) {
            dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
            int x = dp[i];
        }
        else {
            for (int j = 1; j <= k; ++j) {
                if(i-j >= 0) {
                   dp[i] = min(dp[i],dp[i-j] + abs(h[i]-h[i-j]));
                }

            }

        }
    }

}
int32_t main() {
    fio
    int n,k;
    cin >> n >> k;
    int h[n];
    for (int j = 0; j < n; ++j) {
        cin >> h[j];
    }
    path(n,h,k);
//    for (int i = 0; i < n; ++i) {
//        cout << dp[i] << " ";
//    }
    cout << dp[n-1];

}






Measured memory_bytes: 4608
#include <iostream>

using namespace std;

#define MAX_N (1000000)

bool is_prime[MAX_N];
int sum[MAX_N + 1];

int main()
{
    int n;
    
    for (int i = 0; i < MAX_N; i++){
        is_prime[i] = true;
    }
    
    is_prime[0] = false;
    is_prime[1] = false;
    
    for (int i = 4; i < MAX_N; i += 2){
        is_prime[i] = false;
    }
    
    for (int i = 3; i * i < MAX_N; i += 2){
        for (int j = i + i; j < MAX_N; j += i){
            is_prime[j] = false;
        }
    }
    
    sum[0] = 0;
    for (int i = 0; i < MAX_N; i++){
        sum[i + 1] = sum[i] + is_prime[i];
    }
    
    while (cin >> n){
        cout << sum[n + 1] << endl;
    }
}

Measured memory_bytes: 6044
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <stack>
#include <queue>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  std::string S;
  std::cin >> S;

  int X = 0;

  std::string mae;
  std::string usi;

  int Q;
  std::cin >> Q;
  for (int q = 0; q < Q; ++q) {
    int T;
    std::cin >> T;
    if (T == 1) {
      X += 1;
      X %= 2;
    } else {
      int F;
      char C;
      std::cin >> F >> C;
      if (F == 1) {

        if (X == 0) {
          mae.push_back(C);
        } else {
          usi.push_back(C);
        }

      } else {

        if (X == 0) {
          usi.push_back(C);
        } else {
          mae.push_back(C);
        }

      }
    }
  }

  std::reverse(mae.begin(), mae.end());

  std::string res = mae + S + usi;

  if (X == 1)
    std::reverse(res.begin(), res.end());

  std::cout << res << std::endl;

  return 0;
}


Measured memory_bytes: 1348
#include<cstdio>

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

    scanf ("%d %d %d",&a,&b,&c);

    int h,m;
    if (a < b){
        h = a;
        m = b;
    } else {
        h = b;
        m = a;
    }

    int p,q;
    if (m < c){
        p = m;
        q =c;
    }else {
        p = c;
        q = m;
    }
    int x,y;
    if (h < p){
        x = h;
        y = p;
    }else {
        x = p;
        y = h;
    }

    printf ("%d %d %d\n",x,y,q);
}


Measured memory_bytes: 2728
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll INF=1e18;

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}


int main(){
  ll n;
  cin>> n;
  
  const auto &res=prime_factorize(n);
  
  ll ans =0;
  for (auto p :res){
    //cout<<p.first<<" "<<p.second<<endl;
    ll p0=p.second;
    bool judge=true; // 数が多くなればアウト
    ll cnt=1;
    while(judge){
      if(cnt>p0){
       judge=false; 
       break;
      }else{
        ans++;
        p0-=cnt;
        cnt++;
      }
    }
  }
  
  cout<<ans<<endl;
 

}

Measured memory_bytes: 3632
import itertools


def main():
    S = input()
    ans = 0
    for p in itertools.product(("", "+"), repeat=len(S)-1):
        p = list(p) + ['']
        fig = "".join([a+b for a, b in zip(S, p)])
        ans += eval(fig)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 39280
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define ll_MAX LONG_LONG_MAX
#define ll_MIN LONG_LONG_MIN
#define pi pair<ll, ll>
#define endl "\n"
#define MAXN 100005
#define mod 1000000007
using namespace std;
bool is_hor_vert(ll x, ll y, ll x1, ll y1)
{
    if((x1-x) == 0 && (y1-y) == 1)
    {
        return true;
    }
    else if((x1-x) == 0 && (y1 - y) == -1)
    {
        return true;
    }
    else if((y1 - y) == 0 && (x1 - x) == 1)
    {
        return true;
    }
    else if((y1 - y) == 0 && (x1 - x) == -1)
    {
        return true;
    }
    return false;
}
bool check(ll x, ll y, ll h, ll w)
{
    if(x >=1 && x<=h && y>=1 && y<=w)
        return true;
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    ll h,w;
    cin>>h>>w;
    ll c_h,c_w;
    cin>>c_h>>c_w;
    ll d_h, d_w;
    cin>>d_h>>d_w;
    vector<string> S;
    for (ll i = 0; i < h; i++)
    {
        string s;
        cin>>s;
        S.push_back(s);
    }
    deque<pi> q;
    q.push_front(make_pair(c_h, c_w));
    vector< vector<ll> > d(h + 1, vector<ll>(w + 1, ll_MAX) );
    d[c_h][c_w] = 0;
    while(!q.empty())
    {
        ll x = q.front().first;
        ll y = q.front().second;
        q.pop_front();
        for(ll i=-2; i<=2; i++)
        {
            for(ll j=-2; j<=2; j++)
            {
                ll x1 = x + i;
                ll y1 = y + j;
                if(i == 0 && j == 0)
                    continue;
                if(check(x1, y1, h, w))
                {
                    if( S[x1 - 1][y1 - 1] == '.')
                    {
                        if(!is_hor_vert(x, y, x1, y1))
                        {
                            if(d[x1][y1] > (d[x][y] + 1))
                            {
                                d[x1][y1] = d[x][y] + 1;
                                q.push_back(make_pair(x1, y1));
                            }
                        }
                        else if(d[x1][y1] > d[x][y])
                        {
                            d[x1][y1] = d[x][y];
                            q.push_front(make_pair(x1, y1));
                        }
                    }
                }
            }
        }
    }
    if(d[d_h][d_w] != ll_MAX)
    {
        cout<<d[d_h][d_w]<<'\n';
    }
    else
    {
        cout<<-1<<'\n';
    }
    
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;

int memo[25][2005];

bool rec(int ix, int val, vector<int>& v)
{
  if (val == 0) { return true; }
  if (ix >= v.size()) { return false; }
  if (memo[ix][val] != -1) { return memo[ix][val]; }
  if (v[ix] <= val) {
    if (rec(ix + 1, val - v[ix], v)) {
      memo[ix][val] = 1;
      return true;
    }
  }
  bool ret = rec(ix + 1, val, v);
  memo[ix][val] = ret ? 1 : 0;
  return ret;
}

int main()
{
  int n;
  fscanf(stdin, "%d", &n);
  vector<int> A(n);
  for (int i = 0; i < n; ++i) {
    fscanf(stdin, "%d", &A[i]);
  }
  int q;
  fscanf(stdin, "%d", &q);
  memset(memo, -1, sizeof(memo));
  for (int i = 0; i < q; ++i) {
    int val = 0;
    fscanf(stdin, "%d", &val);
    fprintf(stdout, "%s\n", rec(0, val, A) ? "yes" : "no");
  }
  return 0;
}

Measured memory_bytes: 1392
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    int n;
    cin >> n;
    set<string> s;
    REP(i,n){
        string S;
        cin >> S;
        s.insert(S);
    }
    cout << s.size();

    return 0;
}

Measured memory_bytes: 19116
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	h := make([]int, n)
	for i := range h {
		fmt.Scan(&h[i])
	}

	max := 0
	for i := 0; i < n; i++ {
		if h[i] > max {
			max = h[i]
		}
		if max-h[i] > 1 {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


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

using namespace std;
using LL = long long;

int main()
{
    std::cout << std::setprecision(20);
    
    int N;cin >> N;
    vector<pair<double, pair<int, int>>> vec;
    for(int i = 0;i < N;i++){
        int b,c;cin >> b >> c;
        if(b == 0 && c == 0)vec.push_back(make_pair(0, make_pair(b, c)));
        else vec.push_back(make_pair(atan2(c, b), make_pair(b, c)));
    }
    //cout<<"Uku"<<endl;
    sort(vec.begin(), vec.end());
    vector<pair<LL, LL>> ruiseki;
    ruiseki.push_back({0, 0});
    for(int i = 0;i < vec.size();i++){
        ruiseki.push_back({ruiseki.back().first + vec.at(i).second.first, ruiseki.back().second + vec.at(i).second.second});
    }
    for(int i = 0;i < vec.size();i++){
        ruiseki.push_back({ruiseki.back().first + vec.at(i).second.first, ruiseki.back().second + vec.at(i).second.second});
    }

    LL ans = 0;
    for(int i = 0;i < ruiseki.size()-1;i++){
        for(int j = i+1;j < ruiseki.size();j++){
            if(j - i > N)break;
         //   cout<<i<<" "<<j<<endl;
            LL x = ruiseki.at(j).first - ruiseki.at(i).first;
            LL y = ruiseki.at(j).second - ruiseki.at(i).second;
            //cout<<i<<" "<<j<<endl;
            ans = max(ans, (LL)pow(x, 2) + (LL)pow(y, 2));
        }
    }
    cout<<sqrt(ans)<<endl;
    return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vll vector<ll>
#define ub upper_bound
#define lb lower_bound
#define all(v) ((v).begin()),((v).end())
#define ff first
#define ss second
#define mp make_pair
#define pll pair<ll,ll> 
#define fo(i,n) for(ll i=0;i<n;i++)
ll mod1 = 1e9 + 7;
ll mod2 = 998244353;
ll mul(ll x,ll y){
    return (1ll* (x%mod1)*(y%mod1));
}
ll power(ll x,ll y){ll z=1;while(y>0){if(y%2)z=mul(z,x);x =mul(x,x) ;y/=2;}return z;}
ll gcd(ll a,ll b){if(a<b) return gcd(b,a);if(b==0) return a;return gcd(b,a%b);} 
ll min(ll a,ll b){if(a<b)return a;return b;}
ll max(ll a,ll b){if(a>b)return a;return b;}

ll fact[100001];
void facto(){ 
    fact[0]=1;
	for(ll i=1;i<100001 ; i++){
    	fact[0]=1;
    	fact[i] = mul(i,fact[i-1]);
    
}
}
ll inv(ll n){
    return power(n,mod1-2);
    
}
ll divide(ll x,ll y){
    return mul(x,inv(y));
}
ll ncr(ll n,ll r){
    return divide(fact[n],mul(fact[n-r],fact[r]));
}





int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    //freopen("error.txt" , "w" , stderr) ;
    #endif
    
    ll n,k;
    cin>>n>>k;
    ll a[n+1];
    fo(i,n+1){
        a[i] = i;
    }
    ll sum[n+1];
    sum[0] = 0;
    fo(i,n){
        sum[i+1] = sum[i] + a[i+1];
    }
    ll ans = 0;
    
    //cout<<in<<endl;
    ll d = n-k+1;
    if(d==-1){
        cout<<1<<endl;
        return 0;
    }
    for(ll i = k;i<=n;i++){
        ans+= sum[n] - sum[n-i] - sum[i-1] + sum[0] + 1;
        ans%= mod1;
    }
    ans++;
    cout<<ans%mod1<<endl;

}

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(6);
    /*start*/
    ll a, b, k;
    cin >> a >> b >> k;
    if (a > 0)
    {
        if (a > k)
        {
            a -= k;
            k = 0;
        }
        else
        {
            k -= a;
            a = 0;
        }
    }
    if (k > 0)
    {
        if (b > k)
        {
            b -= k;
            k = 0;
        }
        else
        {
            k -= b;
            b = 0;
        }
    }
    cout << a << " " << b;
    ed;
    return 0;
}

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

#define for_(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long lint;
template<typename T > void modMul(T& a, T b, T m) { a = (a*b)%m; }
template<typename T > void modAdd(T& a, T b, T m) { a = (a+b)%m; }

const lint MOD = (lint)1e9 + 7;

lint power(lint x, int k) {
	lint res = 1;
	while (k) {
		if (k & 1) modMul(res, x, MOD);
		modMul(x, x, MOD);
		k >>= 1;
	}
	return res;
}

int main() {
	int H, W, A, B;
	cin >> H >> W >> A >> B;
	
	int S = H+W+10;
	vector< lint > fact(S, 0);
	fact[1] = 1;
	for_(i,2,S) fact[i] = (fact[i-1] * i) % MOD;
	
	vector< lint > inv(S, 0);
	for_(i,1,S) inv[i] = power(fact[i], MOD-2);
	
	auto nCk = [&](int n, int k) {
		if (k == 0 || n == k) return 1LL;
		lint res = fact[n];
		modMul(res, inv[n-k], MOD);
		modMul(res, inv[k], MOD);
		return res;
	};
	
	lint ans = 0;
	for_(i,B,W) {
		lint add = nCk(H-A-1+i, i);
		modMul(add, nCk(A-1+W-1-i, W-1-i), MOD);
		modAdd(ans, add, MOD);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>
#include <bitset>

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

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

const ll MOD = 1000000007;
const int INF = 1<<30;
//const ll INF = (ll)1e18 + 1;

int main(){
  int N; cin >> N;
  ll a[310][310], dp[310][310];
  rep(i, N) rep(j, N) cin >> a[i][j], dp[i][j] = a[i][j];

  rep(k, N) rep(i, N) rep(j, N){
    if (i == j || j == k || k == i || dp[i][k] == INF || dp[k][j] == INF) continue;
    if (dp[i][k] + dp[k][j] == a[i][j]) dp[i][j] = INF;
    else if (dp[i][k] + dp[k][j] < a[i][j]){
      cout << -1 << endl;
      return 0;
    }
  }

  ll sum = 0;
  for (int i = 0; i < N; ++i){
    for (int j = i + 1; j < N; ++j){
      if (dp[i][j] != INF) sum += dp[i][j];
    }
  }
  cout << sum << endl;
}


Measured memory_bytes: 1664
#include<iostream>
using namespace std;
string s,t;
main()
{
	cin>>s>>t;
	for(int i=s.size();i--;)
	{
		if(i+t.size()>s.size())continue;
		bool flag=1;
		for(int j=0;j<t.size();j++)
		{
			if(!(s[i+j]=='?'||s[i+j]==t[j]))
			{
				flag=0;
				break;
			}
		}
		if(flag)
		{
			for(int j=0;j<t.size();j++)
			{
				if(s[i+j]=='?')s[i+j]=t[j];
			}
			for(int j=0;j<s.size();j++)if(s[j]=='?')s[j]='a';
			cout<<s<<endl;
			return 0;
		}
	}
	cout<<"UNRESTORABLE"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 1e5
#define INF 1<<30
constexpr ll mod = 1e9 + 7;
using namespace std;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

template<ll mod>
class Fp {
public:
	ll val;

private:
	inline void calc_mod(ll& v) {
		if (v >= mod)v -= mod;
	}
public:
	Fp() {}
	Fp(ll v) :val(v%mod) {
		if (val < 0)val += mod;
	}

	Fp operator+=(const Fp &in) {
		val += in.val;
		calc_mod(val);
		return *this;
	}

	Fp operator+(const Fp &in) const {
		return Fp(*this) += in;
	}

	Fp &operator-=(const Fp &in) {
		val -= in.val;
		calc_mod(val);
		if (val < 0)val += mod;
		return *this;
	}

	Fp operator-(const Fp &in) const {
		return Fp(*this) -= in;
	}

	Fp& operator*=(const Fp& in) {
		val = val * in.val % mod;
		return *this;
	}

	Fp operator*(const Fp &in) const {
		return Fp(*this) *= in;
	}

	Fp& operator/=(const Fp& in) {
		*this *= modpow(in, mod - 2);
		return *this;
	}

	Fp operator/(const Fp& in) const {
		return Fp(*this) /= in;
	}

	bool operator==(const Fp&in)const {
		return val == in.val;
	}

	bool operator!=(const Fp&in)const {
		return val != in.val;
	}

	friend Fp modpow(const Fp& in, ll n) {
		if (n == 0)return 1;
		if (n & 1) {
			return in * modpow(in*in, n / 2);
		}
		else {
			return modpow(in*in, n / 2);
		}
	}
};
using modll = Fp<mod>;

class Factorial {
public:
	vector<modll> fact, finv;
	Factorial(ll n) :fact(n + 1, modll(1)), finv(n + 1, modll(1)) {
		for (int i = 2; i <= n; i++) {
			fact[i] = fact[i - 1] * i;
			finv[i] = finv[i - 1] / i;
		}
	}

	modll com(const ll& n, const ll& k) {
		if (n < k || n < 0 || k < 0)return modll(0);
		return fact[n] * finv[k] * finv[n - k];
	}
};


int main() {
	while (cin >> N >> A >> B >> C) {
		Factorial f(2 * N);
		modll a = A, b = B;
		modll ans = 0;
		for (M = N; M < 2 * N; M++) {
			ans += f.com(M - 1, N - 1)*(modpow(a, N)*modpow(b, M - N) + modpow(a, M - N)*modpow(b, N))*M * 100 / (modpow(a + b, M) * (100 - C));
		}
		cout << ans.val << endl;
	}
}


Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

const unsigned long long MOD = 1000000007;

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

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

	unsigned long long a=0, b=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i < j && v[i] > v[j]){
				a++;
			}else if(v[i] < v[j]){
				b++;
			}
		}
	}

	unsigned long long ans = (k*a) % MOD;
	unsigned long long tmp;
	if(k % 2 == 0){
		tmp = (k/2) % MOD;
		tmp = tmp*(k-1) % MOD;
	}else{
		tmp = ((k-1)/2) % MOD;
		tmp = tmp*k % MOD;
	}
	tmp = tmp*b % MOD;
	ans = (ans + tmp) % MOD;
	cout << ans << endl; 

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
#include<cstring>
using namespace std;
long long int mod = 1e9 + 7;
template <class T>
void inputV(vector<T> &x, int n){
  for(int i=0; i<n; i++) cin >> x[i];
}
int n, m;
vector< vector<int> > d;

int main() {
  cin >> n >> m;
  d.resize(n, vector<int>(n, 1e9));
  vector<int> a(m);
  vector<int> b(m);
  vector<int> c(m);
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i] >> c[i];
    a[i]--; b[i]--;
    d[a[i]][b[i]] = c[i];
    d[b[i]][a[i]] = c[i];
  }

  for(int i=0; i<n; i++) d[i][i] = 0;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      for(int k=0; k<n; k++){
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
      }
    }
  }

  int cnt = 0;
  for(int i=0; i<m; i++){
    int f = 0;
    for(int j=0; j<n; j++){
      if(d[j][a[i]] + c[i] == d[j][b[i]]) f = 1;
    }
    cnt += f;
  }
  cout << m - cnt << endl;

  return 0;
}



///


Measured memory_bytes: 256
// Sky's the limit :)
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int T = 1; 
    // cin >> T; 
    while (T--) {
        int n; 
        cin >> n;
        
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += (i + 1) * (n - i);
        
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            if (u > v) 
                swap(u, v);
            ans -= u * (n + 1 - v);
        }

        cout << ans << '\n';
        
    }
    
    return 0;
}



Measured memory_bytes: 3652