akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
struct Edge{
    int dst, cap, rev, ori;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

bool used[1010];
int N, M, S, T;
Graph G;

bool dfs(int v, bool mode=true) {
    if(v == T) {
        return true;
    }
    if(used[v]) return 0;
    used[v] = true;
    for(Edge& e : G[v]) if(e.cap) {
        if(dfs(e.dst, mode)) {
            if(mode) {
                e.cap = 0;
                G[e.dst][e.rev].cap = 1;
            }
            return true;
        }
    }
    return false;
}

void rec(int v, int c, bool used_rec[1010]) {
    if(used_rec[v]) return;
    used_rec[v] = true;
    for(const Edge &e : G[v]) if(e.cap == c) {
        rec(e.dst, c, used_rec);
    }
}


int main(){
    while(cin >> N >> M >> S >> T && N > 0) {
        S--; T--;
        G.assign(N, Node());
        REP(i, M) {
            int a, b;
            cin >> a >> b;
            a--; b--;
            G[a].push_back({b, 1, (int)G[b].size(), 1});
            G[b].push_back({a, 0, (int)G[a].size() - 1, 0});
        }

        int flow = 0;
        while(true) {
            memset(used, 0, sizeof(bool) * N);
            bool f = dfs(S);
            if(!f) break;
            flow ++;
        }

        bool A[1010] = {};
        rec(S, 1, A);
        bool B[1010] = {};
        rec(T, 0, B);

        int ans = 0;
        REP(i, N) for(Edge& e : G[i]) {
            if(e.ori && e.cap) {
                if(A[e.dst] && B[i]){
                    ans++;
                }
            }
        }

        if(ans != 0) {
            flow++;
        }

        cout << flow << " " << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1916
N = int(input())
dp = [-1 for i in range(100010)]

availableValues = sorted(
    [
        1,
        6,
        36,
        216,
        1296,
        7776,
        46656,
        9,
        81,
        729,
        6561,
        59049,
    ],
    reverse=True)


def solve(n):
    if dp[n] != -1:
        return dp[n]

    ans = 110000
    for i in availableValues:
        if i < n:
            ans = min(ans, solve(n - i) + 1)
        if i == n:
            ans = 1
    dp[n] = ans
    return dp[n]


print(solve(N))


Measured memory_bytes: 3912
N, M = gets.chomp.split(' ').map(&:to_i)
n = Array.new(N, 0)
m = Array.new(M, 1)
nm = n + m

nm_comb = nm.combination(2).to_a.map{|i| i.reduce(:+)}
print(nm_comb.select{|i| i.even?}.size)


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

using namespace std;

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

    vector<int> s;
    int x;
    for(int i=0;i<n;i++)  {
      cin>>x;
      s.push_back(x);
}
    int q;
    cin>>q;

    int count=0;
    int t;

    for(int i=0;i<q;i++){
        cin>>t;
        if(binary_search(s.begin(),s.end(),t))  count++;
    }

    cout<<count<<endl;

    return 0;
}



Measured memory_bytes: 3296
n = int(input())
a = list(map(int, input().split()))

dp=[]
for i in range(n):
	dp.append([0]*n)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])

Measured memory_bytes: 111964
#include <iostream>
#include <utility>
#include <algorithm>
#define ll long long
using namespace std;

ll a[100010],b[100010],cnt,m=0,i,bit[100010],n;
pair<ll, ll> p[100010];
ll sum(ll i){
	ll s = 0;
	while(i>0){
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(ll i, ll x){
	while(i<=n){
		bit[i] += x;
		i += i & -i;
	}
}

int main(){
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a[i];
		m = max(a[i],m);
	}
	
	ll lb=m+1,ub=-1,mid;
	while(lb-ub>1){
		ll x = 0;
		mid = (lb+ub)/2;
		cnt = 0;
		for(i=0;i<n;i++){
			bit[i] = 0;
			if(a[i]>=mid){
				b[i] = 1;
			}else{
				b[i] = -1;
			}
			x += b[i];
			if(x>=0){
				cnt++;
			}
			p[i] = make_pair(x,i);
		}
		bit[n] = 0;
		sort(p,p+n);
		ll now = 1;
		b[p[0].second] =  now;
		for(i=1;i<n;i++){
			if(p[i].first!=p[i-1].first){
				now++;
			}
			b[p[i].second] = now;
		}
		for(i=0;i<n;i++){
			cnt += sum(b[i]);
			add(b[i],1);
		}
		if(cnt<n*(n+1)/4){
			lb = mid;
		}else{
			ub = mid;
		}
	}
	cout << ub << endl;
}


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

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> count(N,0);
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        count[a-1]+=1;
        count[b-1]+=1;
    }

    for(int i=0; i<N; i++){
        cout << count[i] << "\n";
    }
    return 0;
}

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

int mochi[101],m[101];
int lis(int n){
	int maxAll = -1;
	m[0] = 1;
	for(int i = 1;i<n;i++){
		int small = 0;
		for(int j=0;j<i;j++){
			if(mochi[j]<mochi[i]){
				small = max(small,m[j]);
			}
		}
		m[i] = small+1;
		maxAll = max(maxAll,m[i]);
	}
	return maxAll;
}

int main(){
	int n;
	scanf("%d",&n);
	
	for(int i = 0;i<n;i++){
		scanf("%d",&mochi[i]);
	}
	sort(mochi,mochi+n);
	int ans = lis(n);
	if(n==1) ans = 1;
	printf("%d\n",ans);

	return 0;
}

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

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

int w,h,res;
char field[20][20];

void dfs(int x,int y){
	res++;
	field[x][y] = '#';
	for(int i = 0;i < 4;i++){
		int nx = x + dx[i],ny = y + dy[i];
		if(nx >= 0 && nx < h && ny >= 0 && ny < w && field[nx][ny] == '.'){
			dfs(nx,ny);
		}
	}
}

int main(){
	int x,y;
	while(cin >> w >> h,w){
		res = 0;
		getchar();
		for(int i = 0;i < h;i++){
			for(int j = 0;j < w;j++) {
				field[i][j] = getchar();
				if(field[i][j] == '@'){
					x = i;
					y = j;
				}
			}
			getchar();
		}
		dfs(x,y);
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3060
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc=new FastScanner();
		PrintWriter pw=new PrintWriter(System.out);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int X=sc.nextInt();
		pw.println(X<=A+B&&X>=A?"YES":"NO");
		pw.close();
	}
	
	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public int nextInt() {
    	return Integer.parseInt(next());
    }
    
    public long nextLong() {
    	return Long.parseLong(next());
    }
}

Measured memory_bytes: 24532
W, H, N = map(int, input().split())
x1, x2, y1, y2 = 0, W, 0, H
for i in range(N):
    x, y, a = map(int, input().split())
    if a == 1 and x > x1:
        x1 = x
    elif a == 2 and x < x2:
        x2 = x
    elif a == 3 and y > y1:
        y1 = y
    elif a == 4 and y < y2:
        y2 = y
if x2 - x1 <= 0 or y2 - y1 <= 0:
    print(0)
else:
    print((x2-x1)*(y2-y1))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	int n=s.size();
	s+=s;
	rep(i,n){
		if(s.substr(i,n)==t){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 256
from itertools import *
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
dic = dict()
i = 0
for a in permutations(range(1,N+1),N):
    dic[a] = i
    i += 1
print(abs(dic[P]-dic[Q]))

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

#define LEN(x) (int)x.size()
#define ALL(x) x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int MOD = 1000'000'007;
const double EPS = 0.000'000'001;

inline int fcmp(double x, double y)
{ return (x < y + EPS ? (x < y - EPS ? -1 : 0) : 1);}

const int N = 100010;
int dp[N], h[N];
int n, k;

int solve(int i)
{
	if(i == n - 1) return 0;
	if(i >= n) return MOD;

	int& r = dp[i];

	if(r == -1)
	{
		r = MOD;
		for(int j = 1; j <= k; j++)
		{
			int a = solve(i + j) + (i + j < n ? abs(h[i] - h[i + j]) : MOD);
			r = min(r, a);
		}
	}

	return r;
}

int main()
{
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);
	cout.precision(10);
	
	cin >> n >> k;

	memset(dp, -1, sizeof(dp));

	for(int i = 0; i < n; i++) cin >> h[i];

	cout << solve(0) << endl;
	
	//cerr << "Tempo de execucao: " << (double)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Measured memory_bytes: 5760
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val k = sc.nextInt()
    val p = Array(n) { sc.nextInt() }
    var sum = p.take(k).sum()
    var max = sum
    for (i in 0 until n - k) {
        sum -= p[i]
        sum += p[i + k]
        max = maxOf(max, sum)
    }
    println((max + k) / 2.0)
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 60132
#include <stdio.h>

int main(void)
{
    int n;
    while(19)
    {
        scanf("%d",&n);
        if(n==0)break;
        int sum=0;
        int max=-1;
        int min=0x7fffff;
        for(int i=0;i<n;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            if(min>tmp)min=tmp;
            if(max<tmp)max=tmp;
            sum+=tmp;
        }
        printf("%d\n",(sum-max-min)/(n-2));
    }
    return 0;
}

Measured memory_bytes: 1028
///#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
///#define double long double
#define all(x) (x).begin(), (x).end()
#define finout(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
#define X first
#define Y second

using namespace std;
const int MOD = 1e9 + 7;

typedef pair <int, int> pii;
typedef vector <int> vi;
inline int ni() {int x; cin >> x; return x;}
template <class T>
inline T nt() {T x; cin >> x; return x;}
inline void print(){}
template<typename T, typename ...TAIL>
inline void print(const T &t, TAIL... tail) {cout << t; print(tail...);}
inline void input() {return;}
template<typename T, typename ...TAIL>
inline void input(T &t, TAIL&... tail) {cin >> t; input(tail...);}

const int N = 3001;
const int inf = 1e9 + 7;
const double PI = 3.14159265359;

int dp[51][51][51*51];

signed main () {
    ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);
    int n, a;
    cin >> n >> a;
    vi v;
    for (int i = 0; i < n; i++) {
        v.push_back(ni());
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j <= 50 * 50; j++) {
                dp[i + 1][k][j] += dp[i][k][j];
                if  (dp[i][k][j])
                    dp[i + 1][k + 1][j + v[i]] += dp[i][k][j];
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 50 * 50; j++) {
            if (j == a * i) ans += dp[n][i][j];
        }
    }
    cout << ans << '\n';
    return 0;
}




















Measured memory_bytes: 54524
#include<stdio.h>
int main()
{
    long long a,b,k;
    long long i=0;
    scanf("%lld %lld %lld",&a,&b,&k);
    
    if(a>=k)
    {
        printf("%lld %lld",a-k,b);
    }
    else if(a<=k && (a+b)>=k)
    {
        printf("0 %lld",b-(k-a));
    }
    else printf("0 0");
}


Measured memory_bytes: 1716
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
const ll mod=1000000007;
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)

int main() {
  int k,n;cin >> k>> n;
  vector<int> a(n);
  int da = 0;
  for(int i=0;i<n;++i) cin >> a[i];
  for(int i=0;i<n-1;++i) da = max(da,a[i+1] - a[i]);
  da = max(da, k+a[0] - a[n-1]);
  cout << k-da << endl;
  return 0;
}


Measured memory_bytes: 1024
///
//  Author : Author
// Created On : Mon Dec 18 2017
//  File : b.cpp
//
#include <cstdint>
#include <iostream>

using namespace std;

int32_t main() {
  int32_t X, Y, Z;
  cin >> X >> Y >> Z;

  cout << (X - Z) / (Y + Z) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;

void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    unsigned long long h;
    cin >> h;
    unsigned long long a = 1;
    unsigned long long ans=0;
    while(h){
        ans  += a;
        if(h%2==0){
            h = h/2;
        }
        else{
            h = (h-1)/2;
        }
        a*=2;
        if(h==1){
            ans += a;
            h=0;
        }
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 3632
function Main(input) {
  // fillメソッドは一番ネストが深いところでのみ使う
  let table = Array.from(new Array(4), () =>
    Array.from(new Array(3), () => new Array(10).fill(0))
  );

  const args = input.trim().split("\n");
  let n = parseInt(args[0]);
  for (let i = 0; i < n; i++) {
    let b, f, r, v;
    // 分割代入!
    [b, f, r, v] = args[i + 1].split(" ").map((x) => Number(x));
    table[b - 1][f - 1][r - 1] += v;
  }

  for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 3; j++) {
      let output = "";
      for (let k = 0; k < 10; k++) {
        output += " ";
        output += String(table[i][j][k]);
      }
      console.log(output);
    }
    if (i !== 3) {
      console.log("####################");
    }
  }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 16292
#include<stdio.h>
int main(void){
  int i;
  char s[101];
  int ct=0;
  
  for(i=0;i<101;i++){
    s[i]=0;
  }
  
  scanf("%s",s);
  
  for(i=0;s[i]!='\0';i++){
    ct++;
  }
  
  printf("%c%d%c\n",s[0],ct-2,s[ct-1]);
  
  return 0;
}



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

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

	int n = s.length();
	int m = t.length();

	vector<int> occ;

	for (int i = 0; i < n; i++)
	{
		if (s[i] == t[0])
		{
			occ.push_back(i);
		}
	}

	for (int i = 0; i < occ.size(); i++)
	{
		bool isPossible = false;
		int index = occ[i];

		for (int j = 0; j < m; j++)
		{
			if (s[index] != t[j])
			{
				isPossible = false;
				break;
			}
			else
			{
				isPossible = true;
				index++;
			}

			if (index >= n)
			{
				index = 0;
			}
		}

		if (isPossible)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}

Measured memory_bytes: 256
//om namah shivaay
//faith over fear
//no one wants to die,yet death is the destination we all share 
// don't think you are,know you are!!

#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main(){
    string s;
    cin>>s;
    cout<<s[0]<<s[1]<<s[2];
}

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



int main()
{
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> l(N), r(N);
    for( int i = 0; i < Q; ++i ) cin >> l[i] >> r[i];
    

    // numAC[i]; 0 ~ i 文字目までに含まれる AC の個数
    vector<int> numAC(N);
    for( int i = 1; i < N; ++i )
    {
        if( S[i-1] == 'A' and S[i] == 'C' ) numAC[i] = numAC[i-1] + 1;
        else numAC[i] = numAC[i-1];
    } 

    for( int i = 0; i < Q; ++i ) cout << numAC[r[i]-1] - numAC[l[i]-1] << endl;

    return 0;
} 

Measured memory_bytes: 2176
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;
    
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>
#define pq priority_queue<ll>
#define rpq priority_queue<ll,vector<ll>,greater<ll>>
    
ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
    
//-------------------------↓↓↓↓↓↓------------------------
    
//------ 自分を天才だと信じる ------
    
int main(void){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>n>>k;
    if(k==1)Cout(0);
    else{
        n--;
        k--;
        n-=k;
        Cout(n);
    }
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int>a(n);
  for(int i=0;i<n;i++)
    cin >> a.at(i);
  sort(a.begin(),a.end());
  int ans=0;
  bool ok=false;
  for(int i=0;i<n;i++)
    ans+=a.at(i);
  if(ans%10==0){
    for(int i=0;i<n;i++){
      if(a.at(i)%10!=0){
        ans-=a.at(i);
        ok=true;
        break;
      }
    }
    if(!ok)
      ans=0;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
N,A,B = list(map(int,input().split()))
listA = list(input())
human = 0
foreign = 0
for i in listA:
    if i == "a":
        if A+B > human:
            human += 1
            print("Yes")
        else:
            print("No")
    elif i == "b":
        if A+B > human and B > foreign:
            human += 1
            foreign += 1
            print("Yes")
        else:
            print("No")
    else:
        print("No")

Measured memory_bytes: 4712
#include<iostream>
#include<algorithm>
#define MAX 100000
using namespace std;

int n, A[MAX+1], L[MAX];

int lis() {
  L[0] = A[0];
  int length = 1;

  for ( int i = 1; i < n; i++ ) {
    if ( L[length - 1] < A[i] )
      L[length++] = A[i];
    else
      *lower_bound(L, L + length, A[i]) = A[i];
  }

  return length;
}

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

  cout << lis() << endl;

  return 0;
}


Measured memory_bytes: 3800
#include<bits/stdc++.h>
typedef long long int lli;

using namespace std;

long long GCD(lli a, lli b){return b ? GCD(b, a%b) : a;}


lli N;
vector<lli> monster;

int main(void){
    cin>>N;
    monster.resize(N);

    for(lli i=0; i<N; i++) cin>>monster[i];

    lli ans = monster[0];
    for(int i=0; i<N; i++){
        ans = GCD(ans, monster[i]);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 1024
v = list(map(int, input().split()))
if v[0]>v[1]:
    v[0], v[1] = v[1], v[0]
if v[1]>v[2]:
    v[1], v[2] = v[2], v[1]
if v[0]>v[1]:
    v[0], v[1] = v[1], v[0]
print(v[0],v[1],v[2])


Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std;
int read()
{
	char c=getchar();int x=0,f=1;
	while(c>'9'||c<'0'){if(c='-'){f=-1;}c=getchar();}
	
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
int main()
{
	int a;cin>>a;
	cout<<a*(a+1)/2<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;
constexpr LL kInf = 1e18;

LL add(LL a, LL b) { return (a + b) % kMod; }

int main() {
  int H, W; cin >> H >> W;
  vector<string> a(H);
  for (int i = 0; i < H; ++i) cin >> a[i];

  vector<vector<LL>> dp(H, vector<LL>(W));
  dp[0][0] = 1;
  for (int c = 1; c < W; ++c)
    dp[0][c] = (a[0][c] == '.') ? dp[0][c-1] : 0;
  for (int r = 1; r < H; ++r)
    dp[r][0] = (a[r][0] == '.') ? dp[r-1][0] : 0;

  for (int r = 1; r < H; ++r) {
    for (int c = 1; c < W; ++c) {
      dp[r][c] = (a[r][c] == '.') ? add(dp[r-1][c], dp[r][c-1])
                                  : 0;
    }
  }
  cout << dp[H-1][W-1] << endl;
}


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

int main()
{
     int T;
     map<string,int>mp;
     mp["AC"]=0; mp["WA"]=0;  mp["TLE"]=0;  mp["RE"]=0;
     cin>>T;
     for(int i=0;i<T;i++)
     {
          string str;
          cin>>str;
          mp[str]++;
     }

     cout<<"AC x "<<mp["AC"]<<"\n";
     cout<<"WA x "<<mp["WA"]<<"\n";
     cout<<"TLE x "<<mp["TLE"]<<"\n";
     cout<<"RE x "<<mp["RE"]<<"\n";

     return 0;
}

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

#define F first 
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 210, M = 10;

int n, m;
int w[N][N], g[N][N];
int d[M][M];

int main()
{
	cin >> n >> m;
	for (int i = 0; i < M; i ++ )
		for (int j = 0; j < M; j ++ )
			cin >> w[i][j];
			
	for (int i = 0; i < n; i ++ )
		for (int j = 0; j < m; j ++ )
			cin >> g[i][j];
	
	for (int k = 0; k < M; k ++ )
		for (int i = 0; i < M; i ++ )
			for (int j = 0; j < M; j ++ )
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
				
	// for (int i = 0; i < M; i ++ )
	// {
		// for (int j = 0; j < M; j ++ )
			// cout << w[i][j] << ' ';
		// puts("");
	// }
	
	int res = 0;
	for (int i = 0; i < n; i ++ )
		for (int j = 0; j < m; j ++ )
			if (g[i][j] != -1 && g[i][j] != 1)
				res += w[g[i][j]][1];
				
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 384
//Ilm kave oi, you know ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)3e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e12;
int n, a[MAXN], b[MAXN];
bool check(int mid)
{
	for (int i = 0; i < n; i++)
		b[i] = (a[i] >= mid);
	
	int ptr = n / 2;
	int l = -1, r = n;
	for (int i = ptr; i < n - 1; i++)
		if(b[i] == b[i + 1])
		{
			r = i;
			break;
		}
	for (int i = ptr; i >= 1; i--)
		if(b[i] == b[i - 1])
		{
			l = i;
			break;
		}
	if(l == -1 && r == n)
		return b[0];
	if(ptr - l < r - ptr)
		return b[l];
	else
		return b[r];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	n = n * 2 - 1;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int L = 1, R = n + 1;
	while(R - L > 1)
	{
		int mid = (L + R) >> 1;
		if(check(mid))
			L = mid;
		else
			R = mid;
	}
	cout << L;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define ARRAY_LENGTH(array) sizeof(array)/sizeof(*array)
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 int INF = 1000100100;

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

    ll ans = 0;
    ll min = INF;
    REP(i, N) {
        ll P;
        cin >> P;

        if(P <= min) {
            ++ans;
            min = P;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3596
#include<cstdio>
#include<set>
using namespace std;
const int MAXN=20005;

int A[MAXN],B[MAXN];

int main()
{
	int N,mn=0x7FFFFFFF;
	long long ans=0;
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d%d",A+i,B+i);
	bool flag=true;
	for(int i=1;i<=N;i++)
	{
		ans+=1LL*A[i];
		if(A[i]!=B[i])
			flag=false;
		if(A[i]>B[i])
			mn=min(mn,B[i]);
	}
	ans-=mn;
	if(flag)
		puts("0");
	else
		printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
  	Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int array[] = new int[n];
    for(int i = 0; i < n; i++)
      array[i] = sc.nextInt();
    
    
    int count = 0;
    while(true){
      if(maxArray(array) == 0) break;
      int i = 0;
      while (i < n) {
        if (array[i] == 0) i++;
        else{
          count++;
          while (i < n && array[i] > 0){
            array[i]--;
            i++;
          }
        }
      }
    }
    System.out.println(count);
  }
  
  static int maxArray(int array[]){
    int max = 0;
    for(int i = 0; i < array.length; i++)
      if(max < array[i]) max = array[i];
    return max;
  }
}

Measured memory_bytes: 21972
#include <stdio.h>
#include <string.h>
//単語を読みとる　小文字化　照合 cntを＋＋

int main(){
    char w[10]={};
    char end[12]="END_OF_TEXT";
    scanf("%s",w);
    int i,cnt=0;
    while(1){
        char t[1000]={};
        scanf("%s",t);
        
        if(strcmp(t,end) == 0)break;
        if (strcmp(t, "END_OF_TEXT\n") == 0) break;
        for(i=0;i<strlen(t);i++)
            t[i]=tolower(t[i]);
        
        if(strcmp(t,w)==0)
            cnt++;

    }
    printf("%d\n",cnt);
    
}


Measured memory_bytes: 2072
#include<bits/stdc++.h>
using namespace std;
#define pb          push_back
#define m_p			make_pair
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i =a, i>=b;i--)
#define sz(x)       (int)x.size()
#define F			first
#define S			second
#define debug(x)	for(int i=0;i<x;i++) cout<<"##########"<<endl
#define M			1000000007
#define ll			long long int
#define lMax		LLONG_MAX
#define pii 		pair<int ,int >
#define	all(a)		a.begin(), a.end()
#define vi 			vector<int> 
#define vii 		vector<pii>

// queue<int> , prefix_sum(a,a+n) , reverse(a,a+n) , priority_queue <int> max heap , priority_queue <int, vector<int>, greater<int> > min heap;
// == > != precedence gretaer then & , << precedence greater than <= == => , 
//int chk, cnt, fl, pos, in, src, tar, val, res. dummy;  fill (myvector.begin(),myvector.begin()+4,5), freq;

void solve()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	
	rep(i,0,n) cin>>a[i]>>b[i]>>c[i];
	int dp[3][n];
	
	dp[0][0]=a[0];
	dp[1][0]=b[0];
	dp[2][0]=c[0];

	rep(i,1,n)
	{
		dp[0][i]=a[i]+max(dp[1][i-1],dp[2][i-1]);
	    dp[1][i]=b[i]+max(dp[0][i-1],dp[2][i-1]);
	    dp[2][i]=c[i]+max(dp[0][i-1],dp[1][i-1]);
	}
	cout<<max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]))<<endl;
}

signed main()
{
		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
		int t=1;
		while(t--)
		{
			solve();
		}
}

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

#define maxn 100005
#define inf (int) 2e9
#define ll long long
#define ii pair <int, int>
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define REP(i, a, b) for(int i = a; i >= b; i--)

int n, k;
int a[maxn], f[maxn];

int main() {
    //freopen("main.inp", "r", stdin);
    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 2, n) f[i] = inf;
    FOR(i, 1, n)
       FOR(j, i + 1, min(i + k, n))
           f[j] = min(f[j], f[i] + abs(a[j] - a[i]));
    cout << f[n];
}


Measured memory_bytes: 4408
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimization("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target ("avx2,avx,fma")
#define ll long long int
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define rep(i,l,r) for(i=l;i<r;i++)
#define bep(i,l,r) for(i=l;i>=r;i--)
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pi 3.1415926535897932384626433832
int main()
{
    io;
    ll r;
    cin>>r;
    cout<<(3*r*r);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,rans,mp2[100];
map<ll,ll>mp;
int main(void){
    cin>>n;
    for(int i=2;i<=n;i++){
        ll L=i;
        for(int j=2;j<=L;j++){
            if(L==1)break;
            while(L%j==0&&L!=1){
                //cout<<L<<j<<endl;
                mp[j]++;
                L/=j;
            }
        }
    }
    for(auto x:mp){
        //cout<<x.first<<x.second<<endl;
        mp2[x.second]++;
    }
    for(int i=99;i>0;i--){
        mp2[i-1]+=mp2[i];
    }
    rans+=mp2[74]+mp2[24]*max(0LL,mp2[2]-1)+mp2[14]*(max(0LL,mp2[4]-1))+mp2[4]*max(0LL,(mp2[4]-1))*max(0LL,(mp2[2]-2))/2;
    cout<<rans<<endl;
}


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



int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	int minimum = 100;
	int maximum = -100;
	for(int i = 0; i < n; i++){
		cin >> a.at(i);
		minimum = min(minimum, a.at(i));
		maximum = max(maximum, a.at(i));
	}
	int ans = 0;
	for(int i = minimum; i <= maximum; i++){
		if(i == minimum){
			for(int j = 0; j < n; j++){
				ans += pow(a.at(j) - i, 2);
			}
		}
		else{
			int sum = 0;
			for(int j = 0; j < n; j++){
				sum += pow(a.at(j) - i, 2);
			}
			ans = min(ans, sum);
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define PB push_back
#define F first
#define S second
#define MP make_pair
#define LL long long
#define ULL unsigned long long
#define LB lower_bound
#define MOD1 1000000007
#define MOD2 1000000009
int n, k;
vector<int> ht;
vector<int> dp;
int solve(int pos)
{
    if (pos < 0)
    {
        return 0;
    }

    if (dp[pos] != -1)
    {
        return dp[pos];
    }

    int currans = INT_MAX;

    for (int i = 1; i <= k; i++)
    {
        if (pos - i >= 1)
            currans = min(currans, solve(pos - i) + abs(ht[pos] - ht[pos - i]));
    }

    return dp[pos] = currans;
}
int main()
{
    static const int _ = []() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
        return 0;
    }();

    cin >> n >> k;
    ht.resize(n + 1);
    dp.resize(n + 1);
    fill(dp.begin(), dp.end(), -1);
    dp[0] = 0;
    dp[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> ht[i];
    }
    dp[2] = abs(ht[2] - ht[1]);

    cout << solve(n);

    return 0;
}


Measured memory_bytes: 5760
{-# LANGUAGE OverloadedStrings #-}
import Data.List
import qualified Data.ByteString.Char8 as B

main = breads >>= B.putStrLn . solve . sort

-- |
-- >>> solve [5, 5, 7]
-- "YES"
-- >>> solve [5, 7, 7]
-- "NO"
solve :: [Int] -> B.ByteString
solve [5, 5, 7] = "YES"
solve _ = "NO"

breads :: IO [Int]
breads = unfoldr uff <$> B.getLine
    where
        uff b = check <$> B.readInt b
        check (a, b)
            | B.null b = (a, b)
            | otherwise = (a, B.tail b)


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

for i in range(N):
  if A[i] % 2 != 0:
    continue
  if not (A[i]%3==0 or A[i]%5==0):
    x = False
if x:
  print("APPROVED")
else:
  print("DENIED")

Measured memory_bytes: 9088
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
 int s, m, h;
 
 cin >> s;
 h = s/3600; s%=3600;
 m = s/60; 
 s = s%60;
 cout << h << ":" << m << ":" << s << endl;
  return 0;
}



Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys


def solve(K: int):
    a =[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    print(a[K-1])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
//agrawal117
//chahatagrawal117
#include<bits/stdc++.h>
#define endl '\n'
#define mod 1000000007
typedef long long int ll;
using namespace std;
#define MAX 100005
int main()
{
	string s;
	cin>>s;
	if(s=="ABC")
	cout<<"ARC"<<endl;
	else
	cout<<"ABC"<<endl;
}

Measured memory_bytes: 3628
import sys
def travel(xs,ys,xf,yf,t):
    d=abs(xf-xs)+abs(yf-ys)
    if d>t:
        return False
    else:
        if d%2==t%2:
            return True
        else:
            return False

N=int(input())
txy=[[0,0,0]]
for i in range(N):
    txy.append([int(j) for j in input().split(" ")])

for i in range(N):
    if travel(txy[i][1],txy[i][2],txy[i+1][1],txy[i+1][2],txy[i+1][0]-txy[i][0])==False:
        print("No")
        sys.exit()
print("Yes")


Measured memory_bytes: 21052
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,q;
  	cin>>n>>q;
  	vector<int>a(n);
  	for(int i=0;i<n;i++)cin>>a[i];
  	vector<vector<int> >d(n);
  	vector<int>f(n);
  	vector<int>ans(q);
	vector<vector<int> >id(n);
  	for(int i=0;i<q;i++)
    {
      int l,r;
      cin>>l>>r;
      l--;
      r--;
      d[r].push_back(l);
      id[r].push_back(i);
    }
  	vector<int>p(n+1,-1);
  	for(int i=0;i<n;i++)
    {
      if(p[a[i]]!=-1)
      {
        for(int j=p[a[i]];j<n;j=(j|(j+1)))f[j]-=1;
      }
      p[a[i]]=i;
      for(int j=p[a[i]];j<n;j=(j|(j+1)))f[j]+=1;
  	  for(int j=0;j<d[i].size();j++)
      {
        int lsum=0;
        int rsum=0;
        for(int t=i;t>=0;t=(t&(t+1))-1)rsum+=f[t];
        if(d[i][j]>0)
        {
          for(int t=d[i][j]-1;t>=0;t=(t&(t+1))-1)lsum+=f[t];
        }
        ans[id[i][j]]=rsum-lsum;
      }
    }
  for(auto x:ans)cout<<x<<endl;   
  return 0;
}
     

Measured memory_bytes: 52964
import numpy as np
 
a, b, x = map(int, input().split())
 
if x == a**2*b:
    print(0)
    exit()
 
if x < 1/2*b*a**2:
    a1 = 2*x/(a*b)
    rad = np.arctan(a1/b)
else:
    y = 2*(b-x/a**2)
    rad = np.arctan(a/y)
 
print(90-rad*180/np.pi)

Measured memory_bytes: 27160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  int n, m;
  cin >> n >> m;

  vi a(n);
  priority_queue<int> q;
  rep(i, n) {
    cin >> a[i];
    q.push(a[i]);
  }

  rep(i, m) {
    int t = q.top();
//    cerr << t << endl;
    q.pop();
    q.push(t/2);
  }

  ll ans = 0;
  while (q.size()) {
    ans += q.top();
    q.pop();
  }

  cout << ans << endl;
}


Measured memory_bytes: 1276
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n) 

int main(void){  
  int n;
  cin >> n;
  REP(i,n){
    string num1s;
    string num2s;
    cin >> num1s >> num2s;
    if(num1s.size()>80||num2s.size()>80)
      cout << "overflow" << endl;
    else{
      int num1[81] = {0}, num2[81] = {0}, sum[81] = {0} ;
      REP(i,num1s.size()) num1[num1s.size()-1-i] = ( num1s[i] - '0' );
      REP(i,num2s.size()) num2[num2s.size()-1-i] = ( num2s[i] - '0' );
      REP(i,80) sum[i] = num1[i] + num2[i];
      REP(i,80) if(sum[i] > 9){
        sum[i+1] += sum[i]/10;
        sum[i] = sum[i]%10;
      }
      if(sum[80] != 0) cout << "overflow" << endl;
      else{
        int first = 79;
        while(sum[first] == 0 && first !=0) first--;
        for(int i=first; i>=0; i--)
          cout << sum[i];
        cout << endl;
      }
    }
  }
}

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

typedef long long ll;

const int N = 200005;

int n,k;
ll a[N],c[N];
int addd[N];

map<ll,int> mp;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i] = c[i-1] + a[i];
	}
	ll ans = 0;
	mp[0] = 1;
	for(int i=1;i<=n;i++){
		if(i-(k-1) > 0){
			mp[addd[i-k]]--;
		}
		int h = (c[i]-i)%k;
		h += k;
		h %= k;
		ans += mp[h];
		
		addd[i] = h;
		//cout<<i<<" "<<c[i]<<" "<<h<<" "<<mp[h]<<" "<<addd[i]<<endl;
		mp[h]++;
		
	}
	
	cout<<ans;
	
	return 0;
}


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

using namespace std;

using ll = long long;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int keta = -1;
	for (int i = 1, x = 10; i < 10; i++) {
		cout << "? " << x << endl;
		char ans;
		cin >> ans;
		if (ans == 'N') {
			keta = i;
			break;
		}
		x *= 10;
	}
	if (keta == -1) {
		ll x = 9;
		for (int i = 1; i <= 10; i++) {
			cout << "? " << x << endl;
			char ans;
			cin >> ans;
			if (ans == 'Y') {
				keta = i;
				break;
			}
			x = x * 10 + 9;
		}
	}
	if (keta == -1) {
		cout << "! 1000000000" << endl;
		return 0;
	}
	ll n = 0;
	for (int i = 0; i + 1 < keta; i++) {
		int ok = (i == 0), ng = 10;
		while (ng - ok > 1) {
			int mid = (ok + ng) / 2;
			cout << "? " << n * 10 + mid << endl;
			char ans;
			cin >> ans;
			if (ans == 'Y') ok = mid;
			else ng = mid;
		}
		n = n * 10 + ok;
	}
	n *= 10;
	int ng = -(keta != 1), ok = 9;
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		cout << "? " << (n + mid) * 10 << endl;
		char ans;
		cin >> ans;
		if (ans == 'Y') ok = mid;
		else ng = mid;
	}
	n += ok;
	cout << "! " << n << endl;
	return 0;
}

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

int main(void) {
  ios::sync_with_stdio(false);
  int A, B, C;
  cin >> A >> B >> C;
  int X = A + B + C;
  int MAX = max(A, max(B, C));
  int Num = MAX;
  if ((X % 2) != (3 * MAX % 2)) {
    Num++;
  }
  int Ans = ((3 * Num) - X) / 2;
  cout << Ans << endl;
  return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;
public class Main {
	public static void main(String[]a) {
		int i,m=0,n=0,p=0,x;
		Scanner s=new Scanner(System.in);
		for(i=0;i<10;i++){
			x=s.nextInt();
			if(m<x){
				p=n;
				n=m;
				m=x;
			}
			else if(n<x){
				p=n;
				n=x;
			}
			else if(p<x)
				p=x;
		}
		System.out.println(m);
		System.out.println(n);
		System.out.println(p);
	}

}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;

int main()
{
	int n, number;
	int sum = 0;
	cin >> n;
	set<int> s;
	for(int i = 0; i < n; i++)
	{
		cin >> number;
		if(s.count(number) == 0)
		{
			s.insert(number);
		}
		else if(s.count(number) == 1)
		{
			s.erase(number);
		}
	}
	cout << s.size() << endl;
	
	
	return 0;
}

Measured memory_bytes: 4864
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    cin >> n;
    cout << n*n*n << "\n";
    return 0;
}

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

using namespace std;

int main() {
	int h,w; cin >> h >> w;
	if(h%3==0||w%3==0) {
		cout << 0 << endl;
		return 0;
	}
	int ans=min(h,w);
	if(w&1) ans=min(ans,max(w/2+h/3,2*(h/3))+1);
	else ans=min(ans,w/2);
	if(h&1) ans=min(ans,max(h/2+w/3,2*(w/3))+1);
	else ans=min(ans,h/2);
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
 
  if (A + B - C - D > 0) {
    cout << "Left" << endl;
  }
  else if (A + B - C - D == 0) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int n,k;
    cin>>n>>k;
    vector<int> A(n+1);
    for(int i=1;i<=n;i++)
        cin>>A[i];
    vector<bool> dp(k+1);
    dp[0]=0;
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(i<A[j])
                continue;
            dp[i]=dp[i]|!dp[i-A[j]];
        }
    }
    
    if(dp[k])
        cout<<"First"<<endl;
    else
        cout<<"Second"<<endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  int a[N], b[N];
  for (int i = 0; i < N; i++) {
      cin >> a[i];
      b[i] = a[i];
  }
  sort(a, a + N);

  int c = a[N / 2];
  int d = a[N / 2 - 1];

  for (int i = 0; i < N; i++) {
    if (b[i] < c) {
      cout << c << endl;
    } else {
      cout << d << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3712
import sys
import itertools
if sys.platform =='win32':
	sys.stdin=open('input.txt')

def MAP(): return [int(x) for x in input().split()]

while True:
	N = int(input())
	K = int(input())

	if N==0 and K==0: break

	a = [int(input()) for _ in range(N)]

	perm = itertools.permutations(a, K)
	nums = []
	for p in perm:
		num = ''
		for s in p:
			num += str(s)
		nums.append(int(num))
	
	print(len(set(nums)))




Measured memory_bytes: 5972
import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)

Measured memory_bytes: 56752
c=list(map(int, input().split()))

if c[0]>=c[2]:
  c[0]-=c[2]
else :
  c[2]-=c[0]
  c[1]-=c[2]
  c[0]=0
  if c[1]<0:
    c[1]=0
print(c[0],c[1])

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<math.h>
using namespace std;

int main(){

    double r;

    cin >> r;

    cout << fixed << setprecision(6) << M_PI * r * r << " " << double(2) * M_PI * r << endl;

    return 0;

}


Measured memory_bytes: 3244
#include <stdio.h>

int main(){
    int n, i;
    scanf("%d", &n);
    int a[n];
    int ans[n];
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
        ans[a[i] - 1] = (i + 1);
    }
    for(i = 0; i < n; i++){
        printf("%d ", ans[i]);
    }
}

Measured memory_bytes: 1536
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	n = readline() |> parseInt
	a = readline() |> split |> parseMap
	a = sort(a)
	k = 0
	for i in 2:n
		if 2*a[i-1] < a[i]
			k = i-1
		end
		a[i] += a[i-1]
	end
	println(n-k)
end
main()


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

string S;
ll Q;

int main() {
  cin >> S >> Q;

  int count = 0;
  string a = "";
  string b = "";

  for (ll i = 0; i < Q; i++) {
    int T;
    cin >> T;
    if (T == 1) {
      count++;
    }
    else {
      int F;
      char add;
      cin >> F >> add;
      if ((count + F) % 2 == 1) {
        a = add + a;
      }
      else {
        b = b + add;
      }
    }
  }
  S = a + S + b;
  if (count % 2 == 1) {
    reverse(S.begin(), S.end());
  }
  cout << S << endl;
}


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

int main()
{
    int a[] = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
    // 配列の添字は 0 から始まるので，a [0] は 0 にしている．
    int x, y;
    cin >> x >> y;
    cout << (a[x] == a[y] ? " Yes " : " No ") << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

int f(string s, int &i) {
    ++i;
    if (isdigit(s[i])) {
        int res = 0;
        while (s[i] != ']') {
            res = 10 * res + (s[i++] - '0');
        }
        ++i;
        res = (res + 1) / 2;
        return res;
    }
    vector<int> v;
    while (s[i] == '[') {
        v.push_back(f(s, i));
    }
    sort(v.begin(), v.end());
    int res = 0;
    REP (j, (v.size() + 1) / 2) res += v[j];
    ++i;
    return res;
}

void _main() {
    int n;
    cin >> n;
    REP (i, n) {
        string s;
        cin >> s;
        int j = 0;
        cout << f(s, j) << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}


Measured memory_bytes: 3312