akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
pair<long,int> D[100000];
int child[100000];
pair<int,int> ans[99999];
long childsum[100000];
void Calc(){
	int N = rei();
	for(int i=0;i<N;i++){
		long d = rel();
		D[i] = {d,i};
	}
	sort(D,D+N);
	for(int i=N-1;i>0;i--){
		long c = D[i].first + 2*child[D[i].second] + 2 - N;
		int bf = 0;
		int bl = N;
		while(bf != bl){
			int bc = (bf+bl)/2;
			if(bc == N || D[bc].first >= c){
				bl = bc;
			}
			else{
				bf = bc+1;
			}
		}
		if(D[bf].first == c){
			child[D[bf].second] += child[D[i].second]+1;
			childsum[D[bf].second] += childsum[D[i].second]+child[D[i].second]+1;
			ans[i] = {D[bf].second,D[i].second};
		}
		else{
			cout << -1 << endl;
			return;
		}
	}
	if(D[0].first != childsum[D[0].second]){
		cout << -1 << endl;
		return;
	}
	for(int i=1;i<N;i++){
		cout << ans[i].first+1 << " " << ans[i].second+1 << endl;
	}
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 4992
using System;
 
class Program
{
  static void Main(string[] args)
  {
    string[] input = Console.ReadLine().Split(' ');
    int a = int.Parse(input[0]);
    int b = int.Parse(input[1]);
    int x = int.Parse(input[2]);
    
    if(a <= x && x <= a + b) Console.WriteLine("YES");
    else Console.WriteLine("NO");
  }
}

Measured memory_bytes: 13140
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)

N, M = map(int, input().split())
uf = UnionFind(N)
ans = 0

for _ in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)

for i in range(1, N+1):
    ans = max(ans, uf.getsize(i))

print(ans)


Measured memory_bytes: 52164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9;
int a[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i=0;i<n;i++)cin >> a[i];
    vector<int> dp(n,1e9);
    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<=i+k;j++){
            if(j<n)dp[j]=min(dp[j],abs(a[i]-a[j])+dp[i]);
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}


Measured memory_bytes: 1024
from itertools import accumulate
from operator import add
x = int(input())
lst = [int(i) for i in input().split()]
a = list(accumulate(lst,add))

s = sum(lst)
b = []
for i in list(a):
  b.append(s - i)

c = []
for i in range(x):
  c.append(abs(b[i] - a[i]))
print(min(c))  


Measured memory_bytes: 38412
#include<stdio.h>

int main(void)
{
    int i, n, ris[100000][2];

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d %d", &ris[i][0], &ris[i][1]);

    int max = 0, num = 0;
    for (i = 0; i < n; i++) 
        if (max < ris[i][0]) {
            max = ris[i][0];
            num = i;
        }

    int ans = max + ris[num][1];
    printf("%d", ans);
    
}


Measured memory_bytes: 896
/******************************************************************************

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

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define mod 1000000007

int main()
{
    int h,w;
    cin>>h>>w;
    long long int b[h][w],i,j,k,l;
    char a[h][w];
    for(i=0;i<h;i++) {
        for(j=0;j<w;j++) {
            cin>>a[i][j];
            if(a[i][j]=='#') b[i][j]=0;
        }
    }
    
    k=1;
    for(i=0;i<h;i++) {
        if(a[i][0]=='#') {
            k=0;
        }
        b[i][0]=k;
    }
    
    k=1;
    for(i=0;i<w;i++) {
        if(a[0][i]=='#') {
            k=0;
        }
        b[0][i]=k;
    }
    
    for(i=1;i<h;i++) {
        for(j=1;j<w;j++) {
            if(a[i][j]=='#' ) b[i][j]=0;
            else {
                b[i][j]=(b[i-1][j]+b[i][j-1])%mod;
            }
        }
    }
    
    cout<<b[h-1][w-1]%mod<<endl;

    return 0;
}


Measured memory_bytes: 12364
#include <stdio.h>
#include <iostream>
#include <iomanip>

int main() {

	double w, h, x, y;
	std::cin >> w >> h >> x >> y;
	std::cout << std::fixed << std::setprecision(6);
	std::cout << w * h / 2 << ' ';
	(x == w / 2 && y == h / 2) ? puts("1") : puts("0");

	return 0;
}

Measured memory_bytes: 256
import Data.Char  -- ord, chr
import Data.List  -- isInfixOf

decaesar cipher shift = map (charshift shift) cipher
charshift shift c
  | 'a' <= c && c <= 'z' = chr ((ord c - ord 'a' + shift) `mod` 26 + ord 'a')
  | otherwise            = c

containsKeyword str = or $ map (`isInfixOf` str)  ["the", "this", "that"]

decrypt cipher =
  head . filter containsKeyword . map (decaesar cipher) $ [0..25]

main = do
  s <- getContents
  putStr . unlines . map decrypt . lines $ s

Measured memory_bytes: 3880
#include <iostream>
#include <cstring>

using namespace std;
const int NMAX = 1005;
char s[NMAX], t[NMAX];
int n, l;

int score(int val) {
    int cnt = 0;
    for(int i = 0; i < l; i++) {
        if(t[i] == s[val + i])
            cnt++;
    }
    return cnt;
}


int main()
{
    cin.getline(s, NMAX);
    cin.getline(t, NMAX);
    n = strlen(s); l = strlen(t);
    int nmax = n * 20;
    for(int i = 0; i < n - l + 1; i++) {
        int x = l - score(i);
        if(x < nmax)
            nmax = x;
    }
    cout << nmax;
    return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  int n;
  int i;
  ll sum=0;
  ll card[100005]={};
  int a;

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

  rep(i,n){
    if(card[i]%2 && card[i+1]>0){
      sum++;
      card[i]--;
      card[i+1]--;
    }
    if(card[i]>0)
      sum+=card[i]/2;
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 1024
N = int(input())
A_list = list(map(int,input().split()))
B_list = list(map(int,input().split()))
C_list = list(map(int,input().split()))
ans = 0
for i in range(N):
    ans += B_list[A_list[i]-1]
    
    if i < N-1:
        if A_list[i]+1==A_list[i+1]:
            ans += C_list[A_list[i]-1]
print(ans)

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

int main(){

	int a, b;
	char op;

	while (true){
		cin >> a >> op >> b;

		if (op == '?'){
			break;
		}
		if (op == '+'){
			cout << a + b << endl;
		}
		if (op == '-'){
			cout << a - b << endl;
		}
		if (op == '*'){
			cout << a*b << endl;
		}
		if (op == '/'){
			cout << a / b << endl;
		}

	}


	return 0;
}


Measured memory_bytes: 3100
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
string str;
int main(){
    ll x;
    cin >> x;
    cin >> str;
    ll cnt = 0;
    for(ll i=2;i<str.size();i++){
        if(str[i-2]=='A'&&str[i-1]=='B'&&str[i]=='C')   cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

    atmp = -1
    if len(a) != 0:
        atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

Measured memory_bytes: 460404
def resolve():
    n = int(input())
    s = input()
    left = [0] * n
    right = [s[1:].count("E")] + [0] * (n - 1)
    ans = [s[1:].count("E")] + [0] * (n - 1)
    for i in range(1, n):
        left[i] = left[i - 1] + (1 if s[i - 1] == "W" else 0)
        right[i] = right[i - 1] + (-1 if s[i] == "E" else 0)
        ans[i] = left[i] + right[i]
    print(min(ans))


if __name__ == "__main__":
    resolve()


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

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

using namespace std;

int findSumOfDigits(int n){
            int sum = 0;
            while(n > 0){
                sum += n % 10;
                n /= 10;
            }
            return sum;
        }

int main() {

    int num,min,max;
    
    cin >> num >> min >> max;
    int total = 0;
    

        for(int i = 1; i <= num; i++){
            int sum = findSumOfDigits(i);
        if(sum >= min && sum <= max){
            total += i;
        }
    }
    
    cout << total << endl;    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define endl '\n'
int main(){
    ll n,m;
    cin>>n>>m;
    ll x=n%m;
    ll y=m-x;
    ll ans=min(x,y);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
// #include <algorithm>
// #include <set>
// #include <map>
using namespace std;

int main()
{
  // 整数の入力
  // int a;
  // cin >> a;
  // N分、入力を取る
  // int N;
  // cin >> N;
  // int d[100];
  // for (int i = 0; i < N; i++) cin >> d[i];
  // スペース区切りの整数の入力
  // int b, c;
  // cin >> b >> c;
  // 文字列の入力
  string S;
  cin >> S;
  int count = 0;
  char p = S[0];
  for (int i = 1; i < S.length(); i++)
  {
    if (p == S[i])
    {
      count++;
      p = S[i] == '0' ? '1' : '0';
    }
    else
    {
      p = S[i];
    }
  }
  cout << count;
  // 出力
  // cout << (a + b + c) << " " << s << endl;
  return 0;
}

Measured memory_bytes: 512
$n = gets.to_i
$ans = 0

def dfs(current, is_3, is_5, is_7)
  return if current > $n
  $ans += 1 if is_3 && is_5 && is_7
  dfs(current * 10 + 3, true, is_5, is_7)
  dfs(current * 10 + 5, is_3, true, is_7)
  dfs(current * 10 + 7, is_3, is_5, true)
end

dfs(0, false, false, false)
puts $ans


Measured memory_bytes: 1788
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    vector<tuple<int, int, int> > v(m);
    for(int i=0; i<m; ++i){
        int p, y;
        cin >> p >> y;
        v[i] = make_tuple(p, y, i);
    }
    sort(v.begin(), v.end());

    vector<string> ans(m);
    int pPrev = -1;
    int k = -1;
    for(int i=0; i<m; ++i){
        int p, y, j;
        tie(p, y, j) = v[i];
        if(p == pPrev){
            ++ k;
        }
        else{
            k = 1;
            pPrev = p;
        }

        ostringstream oss;
        oss << setw(6) << setfill('0') << p
            << setw(6) << setfill('0') << k;
        ans[j] = oss.str();
    }

    for(int i=0; i<m; ++i)
        cout << ans[i] << endl;

    return 0;
}


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

int a[1000001];

int calc_divisor(int aa)
{
    if (aa != 1 && a[1] > 0)
    {
        return 0;
    }

    // printf("%d ---\n", aa);
    int n = (int)sqrt((double)aa);
    for (int i = 2; i <= n; i++)
    {
        if (aa % i != 0)
        {
            continue;
        }
        // printf("%d, %d\n", i, aa / i);
        if (a[i] > 0 || a[aa / i] > 0)
        {
            return 0;
        }
    }
    return 1;
}

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

    for (int i = 0; i < n; i++)
    {
        int aa;
        scanf("%d", &aa);
        a[aa]++;
    }

    int ans = 0;
    for (int i = 1; i < 1000001; i++)
    {
        if (a[i] == 0 || a[i] > 1)
        {
            continue;
        }
        // printf("%d: %d\n", i, a[i], calc_divisor(a[i]));
        if (calc_divisor(i) == 1)
        {
            ans++;
        }
    }
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 6052
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
vector<vector<int>> g;
queue<pair<int, int>> q;
int n, m, x, kk, k, y, dp[100005][4], start, stop, res;
int main() {
    DAU
    cin >> n >> m;
    g.resize(n + 1);
    while (m--) {
        cin >> x >> y;
        g[x].emplace_back(y);
        //g[y].emplace_back(x);
    }
    cin >> start >> stop;
    q.emplace(start, 0);
    dp[start][0] = 1;
    while (!q.empty()) {
        tie(x, kk) = q.front();
        q.pop();
        k = (kk + 1) % 3;
        for (const int& y : g[x])
            if (dp[y][k] == 0 || dp[x][kk] + 1 < dp[y][k]) {
                dp[y][k] = dp[x][kk] + 1;
                q.emplace(y, k);
            }
    }
    res = dp[stop][0] - 1;
    if (res != -1)
        res /= 3;
    cout << res;
    PLEC
}


Measured memory_bytes: 10352
/*___________Bismillahir Rahmanir Rahim__________*/
//Think positive, be positive and never use negative words
#include<bits/stdc++.h>
#define ll               long long int
#define uni(a)           a.erase(unique(a.begin(),a.end()),a.end())
#define vsum(a)          accumulate(a.begin(),a.end(),0)
#define vmax(a)          *max_element(a.begin(),a.end())
#define vmin(a)          *min_element(a.begin(),a.end())
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define yes              cout<<"YES"<<endl
#define no               cout<<"NO"<<endl;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, b, c, d;
    cin>>a>>b>>c>>d;

    ll x=a*c;
    ll y=a*d;
    ll m=b*c;
    ll n=b*d;
    ll ans=max(x,max(y,max(m,n)));

    cout<<ans<<endl;

    return 0;
}
/*_________________Alhamdulillah_________________*/


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define endl '\n'
#define F first
#define S second
#define all(c) c.begin(), c.end()
#define int long long
#define forn(i,a,b) for (int i=a; i<b; i++)
#define MOD 1000000000+7;

using namespace std;

void solve (){
	int n,m,pe=0;
	cin>>n>>m;
	int A[n],B[n];
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	vector <int> v;
	forn(i,0,m) {
		int a;
		string s;
		cin>>a>>s;
		a--;
		if (s=="AC") A[a]=1;
		else {
			if (!A[a]) B[a]++;
		}
	}
	forn(i,0,n) {
		if (A[i] && B[i]) pe+=B[i];
	}
	cout<<(accumulate(A,A+n,0))<<' '<<pe<<endl;
}

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

Measured memory_bytes: 1792
#include<iostream>
#define f first
#define s second
using namespace std;
int n, m, k, i, j, dir, p, u, ii, jj, iv, jv, sol;
char a[805][805], viz[805][805];
int d[805][805], b[805][805];
pair<int, int> c[805 * 805], srs;
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};
int main(){
    cin>> n >> m >> k;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            cin>> a[i][j];
            if(a[i][j] == 'S'){
                a[i][j] = '.';
                srs = make_pair(i, j);
            }
        }
    }
    viz[srs.f][srs.s] = 1;
    p = u = 1;
    c[1] = srs;
    while(p <= u){
        ii = c[p].f;
        jj = c[p].s;
        p++;
        for(dir = 0; dir < 4; dir++){
            iv = ii + di[dir];
            jv = jj + dj[dir];
            if(a[iv][jv] == '.' && viz[iv][jv] == 0){
                viz[iv][jv] = 1;
                b[iv][jv] = 1 + b[ii][jj];
                c[++u] = make_pair(iv, jv);
            }
        }
    }
    p = 1;
    u = 0;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(viz[i][j] == 1 && b[i][j] <= k){
                c[++u] = make_pair(i, j);
            }
            else{
                viz[i][j] = 0;
            }
        }
    }
    while(p <= u){
        ii = c[p].f;
        jj = c[p].s;
        p++;
        for(dir = 0; dir < 4; dir++){
            iv = ii + di[dir];
            jv = jj + dj[dir];
            if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && viz[iv][jv] == 0){
                viz[iv][jv] = 1;
                d[iv][jv] = 1 + d[ii][jj];
                c[++u] = make_pair(iv, jv);
            }
        }
    }
    sol = n * m;
    for(i = 1; i <= n; i++){
        sol = min(sol, d[i][1]);
        sol = min(sol, d[i][m]);
    }
    for(j = 1; j <= m; j++){
        sol = min(sol, d[1][j]);
        sol = min(sol, d[n][j]);
    }
    if(sol % k != 0){
        sol += k;
    }
    cout<< 1 + sol / k;
}


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

int main() {
	long long L, R; cin >> L >> R;
	long long ans = 2020;
	for (long long i = L; i < R; i++) {
		for (long long j = i + 1; j <= R; j++) {
			if (j % 2019 == 0 || i % 2019 == 0) {
				cout << 0 << endl;
				return 0;
			}
			else {
				long long num = (i % 2019) * (j % 2019) % 2019;
				ans = min(ans, num);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3624
//********************************************************************//
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define fi first 
#define se second 
#define RANGE(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define DFOR(i, a, b) for(int i = a; i > b; --i)
#define DEB(x) cout << #x << ": " << x << endl
#define ALL(v) v.begin(), v.end() 
#define SORT(v) sort(ALL(v))
#define DISPV(v) { for(auto x___: v) cout << x___ << " "; cout << endl; }
#define DISPM(m) { for(auto x____: m){ cout << x____.first << ": " << x____.second << endl; } };
#define DISPMV(m) { for(auto x_____: m){ cout << x_____.first << ": " ;DISPV(x_____.second);} };
using LL = long long;
using VI = vector <int>;
using VC = vector <char>;
using VS = vector <string>;
using VL = vector <long long>;
using VVI = vector<VI>;
using VVL = vector <VL>;
using MII = map<int, int>;
using MIVI = map<int, VI>;
using MSS = map<string, string>;
using MLL = map<LL, LL>;
int READ_INT(){int temp;cin>>temp;return temp;}      // read an int
LL READ_LONG(){LL temp;cin>>temp;return temp;}      // read a long long
void mcs(VI &series, int &max_sum){                    // maximum contigous sub sum(kadane)
    int s=0;
    for(auto x: series){
        s += x;
        max_sum = max(max_sum, s);
        if(s < 0)s = 0;
    }
}
template<typename T>
T MAX(T t){ return t;}
template <typename T, typename... Args>
T MAX(T t, Args... args){ return max(t, MAX(args...)); }
const int MOD = int(1e9) + 7;
const int INF = 1e9 + 5;
const double PI = acos(-1.0); //M_PI;
const double EPS = 1e-9;
//********************************************************************//
 
int main(){
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    LL a, b, c, k;
    cin >> a >> b >> c >> k;

    if(k <= a+b){
        cout << min(a, k);
    }
    else{
        cout << a - (k - a - b);
    } 

    return 0;
}



/* complie flags
-Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -fstack-protector
*/

Measured memory_bytes: 3556
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

using ll = long long;
using ull = uint64_t;
using P = pair<int, int>;
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

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

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

    int n;
    cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n));
    vector<vector<ll>> dist(n, vector<ll>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
            dist[i][j] = a[i][j];
        }
    }
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(a[i][j] != dist[i][j]){
                cout << -1 << endl;
                return 0;
            }
            ans += dist[i][j];
        }
    }
    ans >>= 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < i; ++j){
            bool ok = true;
            for(int k = 0; k < n; ++k){
                if(k == i || k == j)    continue;
                if(dist[i][j] == dist[i][k] + dist[k][j]){
                    ok = false;
                    break;
                }
            }
            if(!ok) ans -= dist[i][j];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4768
S = input()
K = int(input())

# S = "111111111"
# K = 6565

ans = 1
ones = -1

for i in range(len(S)):
    if int(S[i]) == 1:
        pass
    else:
        ans = int(S[i])
        ones = i
        break

if ones == -1:
    ones = len(S) + 1

if K <= ones:
    ans = 1

print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <set>

constexpr int DATA_SIZE = 200;

using ListItr_t = std::multiset<int>::const_iterator;

bool _isAbleMake(ListItr_t begin, ListItr_t end, int sum, int value) {
    for (auto itr = begin; itr != end; ++itr) {
        if (!_isAbleMake(begin, itr, sum + *itr, value)) { continue; }

        return true;
    }

    return sum == value;
}

bool isAbleMake(const std::multiset<int> & list, int value) {
    return _isAbleMake(list.cbegin(), list.cend(), 0, value);
}

int main() {

    int n, q;
    std::multiset<int> A;
    std::vector<int> m;
    m.reserve(DATA_SIZE);

    std::cin >> n;
    int count = n;
    while (count--) {
        int t;
        std::cin >> t;
        A.insert(t);
    }

    std::cin >> q;
    count = q;
    while (count--) {
        int t;
        std::cin >> t;
        m.emplace_back(t);
    }

    for (auto value : m) {
        if (isAbleMake(A, value)) {
            std::cout << "yes" << std::endl;
        } else {
            std::cout << "no" << std::endl;
        }
    }

    return 0;

}

Measured memory_bytes: 3080
import itertools
from copy import copy


def lr(abc):
    return


def check(abc, k):
    for i in range(K + 1):
        for v in itertools.combinations_with_replacement([0, 1, 2], i):
            ABC_ = copy(ABC)
            for j in v:
                ABC_[j] *= 2
            if ABC_[0] < ABC_[1] < ABC_[2]:
                return "Yes"
    return "No"


ABC = list(map(int, input().split()))
K = int(input())

print(check(ABC, K))



Measured memory_bytes: 9336
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<string>
#define rep(i,n,m) for(int i=(n);i<(int)(m);i++)
#define reps(i,n,m) for(int i=(n);i<=(int)(m);i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define fs first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define LB(a,x) lb(all(a), x) - a.begin()
#define UB(a,x) ub(all(a), x) - a.begin()
#define printfdouble(x) printf("%.12f\n",(x))
#define chartoint(c) (int)((c) - '0')
#define chartoll(c) (long long)((c) - '0')
#define MOD 1000000007
#define itn int
#define enld endl
#define ednl endl
#define icn cin
#define Endl endl
#define stirng string
using namespace std;
typedef long long ll;
const double pi = 3.141592653589793;
using Graph = vector<vector<int>>;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b){if(b<a){a=b; return 1;} return 0;}
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    string s,t; cin >> s >> t;
    int ans = SZ(t);
    rep(i,0,SZ(s)-SZ(t)+1){
        int cnt = 0;
        rep(j,0,SZ(t)){
            if(t[j] != s[i+j]) cnt++;
        }
        chmin(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3612
#include <stdio.h>
#include <memory.h>
int map[10][10];
void las(int y,int x){
    map[y][x]=0;
    int i,o,mv[5]={0,1,0,-1,0};
    for(i=0;i<3;i++,mv[1]++,mv[3]--){
        for(o=0;o<4;o++){
            if(y+mv[o]>0 && y+mv[o]<9 && x+mv[o+1]>0 && x+mv[o+1]<9 && map[y+mv[o]][x+mv[o+1]])
                las(y+mv[o],x+mv[o+1]);
        }
    }
}

int main(void){
    int num,i,o,x,y,data=1;
    scanf("%d",&num);
    for(;memset(map,0,sizeof(map)),num;num--){
        for(i=1;i<=8;i++)
            for(o=1;o<=8;o++)
                scanf("%1d",&map[i][o]);
        scanf("%d\n%d",&x,&y);
        las(y,x);
        printf("Data %d:\n",data++);
        for(i=1;i<=8;i++)
            for(o=1;o<=8;o++)
                printf("%d%s",map[i][o],o==8?"\n":"");
    }
    return 0;
}

Measured memory_bytes: 596
# class Solution:
#     def solve(self, a, b, c, s):
#         return str(a + b + c) + " " + s


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, m = inp()
    ans = n * (n-1) // 2 + m * (m-1) // 2
    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 38384
//
//  main.cpp
//  ABC124
//
//  Created by hiroaki on 2019/05/07.
//  Copyright © 2019年 hiroaki. All rights reserved.
//

#include <iostream>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <cmath>
#include <algorithm>
#include <locale>

//pair sort firstに揃う

#define int long long
#define pb(n) push_back(n)
#define For(n,i) for(int (i)=0;(i)<(n);(i)++)
#define Pr(n) cout<<n<<endl;
#define F first
#define S second
#define vector2 vector<vector<int> >
#define index(v,x) find((v).begin(), (v).end(), (x))-(v).begin()
#define ELM 100001 //問題によっては1000000001に変更
using namespace std;

vector<int> F(int x){
    vector<int> v;
    int c=0;
    for (int i=0; i*i<x; i++) {
        if (x%(i+1)==0) {
            if (i+1==x/(i+1)) {
                v.insert(v.begin()+c,i+1);
            }else{
                v.insert(v.begin()+c,i+1);
                v.insert(v.end()-c, x/(i+1));
            }
            c++;
        }
    }
    return v;
}
signed  main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
//    vector<int> a(n);
//    For(n, i){
//        cin >> a.at(i);
//    }
    vector<int> v=F(n);
    int l=v.size();
    int mid=l/2;
    string s = to_string(v[mid]);
    Pr(s.length());
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define asll unsigned long long
#define ll long long //20190711
#define pii pair<int,int>
#define st first
#define nd second
#define jn <<" "<< 			//20190830
#define ml <<endl; 			//20190831->20190903
#define co cout<<           //20190903
asll M=1e9+7;				//20190518->20190821
int n;						//20190831

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	srand(time(0));			//20190709
	int ac=0,tle=0,wa=0,re=0;
	cin>>n;
	string s;
	for(int i=0;i<n;i++){
		cin>>s;
		if(s=="AC"){
			ac++;
		}
		if(s=="WA"){
			wa++;
		}
		if(s=="TLE"){
			tle++;
		}
		if(s=="RE"){
			re++;
		}
	}
	cout<<"AC x "<<ac ml
	cout<<"WA x "<<wa ml
	cout<<"TLE x "<<tle ml
	cout<<"RE x "<<re ml
}



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

N = INT()
task = [LIST() for _ in range(N)]
task = sorted(task, key=lambda x: x[1])
task = [list(x) for x in zip(*task)]

c = 0
for i in range(N - 1):
    if task[1][i] == task[1][i + 1]:
        c += 1
    else:
        if c != 0:
            task[0][i - c:i+1] = sorted(task[0][i - c:i+1])
            c = 0

now_time = 0
for i in range(N):
    now_time += task[0][i]
    if now_time > task[1][i]:
        print("No")
        exit()

print("Yes")

Measured memory_bytes: 124220
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
unordered_set<ll>s;
vector<ll>visited(100001);
void dfs(ll p,ll c,vector<ll>*v)
{
    visited[p]=1;
    s.insert(c);
    for(ll i=0;i<v[p].size();i++)
    {
        ll x=v[p][i];
        if(visited[x]==0)
        {
            dfs(x,c,v);
        }
    }
}
int main()
{
    ll n,m;
    cin>>n>>m;
    vector<ll>v[n];
    for(ll i=0;i<100001;i++)
        visited[i]=0;
    for(ll i=0;i<m;i++)
    {
        ll a,b;
        cin>>a>>b;
        a--,b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(ll i=0;i<n;i++)
    {
        if(visited[i]==0)
            dfs(i,i,v);
    }
    cout<<s.size()-1;
}

Measured memory_bytes: 12236
#include <stdio.h>

int main(void)
{
	int n;
	int c;

	while (scanf("%d", &n), n){
		c = 0;
		while (n != 1){
			if (n % 2) n = n * 3 + 1;
			else n /= 2;

			c++;
		}
		printf("%d\n", c);
	}

	return (0);
}

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

static const int N = 100;
static const int WHITE = 0; //訪問した
static const int GRAY = 1; //訪問中
static const int BLACK = 2; //全て訪問済み

int n, M[N][N]; //頂点の個数、辺のリスト
int color[N], d[N], f[N], tt; //色、発見時刻、完了時刻、時間
int nt[N];

int next(int u) {
	for (int v = nt[u]; v < n; v++) {
		nt[u] = v + 1;
		if (M[u][v]) return v;
	}
	return -1;
}

void dfs_visit(int r) {
	for (int i = 0; i < n; i++) nt[i] = 0;

	stack<int> S;
	S.push(r);
	color[r] = GRAY;
	d[r] = ++tt;

	while (!S.empty()) {
		int u = S.top();
		int v = next(u);
		if (v != -1) {
			if (color[v] == WHITE) {
				color[v] = GRAY;
				d[v] = ++tt;
				S.push(v);
			}
		}
		else {
			S.pop();
			color[u] = BLACK;
			f[u] = ++tt;
		}
	}
}

void dfs() {
	for (int i = 0; i < n; i++) {
		color[i] = WHITE;
		nt[i] = 0;
	}
	tt = 0;
	for (int u = 0; u < n; u++) {
		if (color[u] == WHITE) dfs_visit(u);
	}
	for (int i = 0; i < n; i++) {
		cout << i + 1 << " " << d[i] << " " << f[i] << endl;
	}
}

int main(void) {
	int u, k, v; //頂点番号、出次数、隣接リスト
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			M[i][j] = 0;
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++) {
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}
	dfs();
	return 0;
}


Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ull;
struct RollingHash{
  string S;
  ull B;
  vector<ull> hash,p;
  int len;
  RollingHash(){}
  RollingHash(string S,ull B=1777771):S(S),B(B){init();};
  void init(){
    len=S.length();
    hash.resize(len+1);
    p.resize(len+1);
    hash[0]=0;p[0]=1;
    for(int i=0;i<len;i++){
      hash[i+1]=hash[i]*B+S[i];
      p[i+1]=p[i]*B;
    }
  }
  //S[l,r)
  ull find(int l,int r){
    return hash[r]-hash[l]*p[r-l];
  }
};


signed main(){
  int n,M;
  while(cin>>n>>M,n){
    string e[n];
    for(int i=0;i<n;i++) cin>>e[i];
    string b,t;
    for(int i=0;i<M;i++){
      cin>>t;
      b+=t;
    }
    int x=n/2,y=n-x;
    set<ull> sa;
    set<ull> m[1<<12];
    set<int> ln[400];
    function<void(int,int,string)> dfs=[&](int d,int c,string s){
      if(d==x||d==y){
	RollingHash rh(s);
	ln[s.size()].insert(c);
	m[c].insert(rh.find(0,s.size()));
	sa.insert(rh.find(0,s.size())>>4);
	if(d==y) return;
      }
      for(int i=0;i<n;i++){
	if((c>>i)&1) continue;
	dfs(d+1,c+(1<<i),s+e[i]);
      }
    };
    dfs(0,0,"");
    int len=0;
    for(int i=0;i<n;i++) len+=e[i].size();
    RollingHash rh(b);
    int ans=0;
    for(int i=0;i<=(int)b.size()-len;i++){
      bool flg=0;
      for(int l=0;l<400;l++){
	if(ln[l].empty()) continue;
	ull u=rh.find(i,i+l),v=rh.find(i+l,i+len);
	if(!sa.count(u>>4)||!sa.count(v>>4)) continue;
	for(int j:ln[l]){
	  int k=(~j)&((1<<n)-1);
	  if(m[j].count(u)&&m[k].count(v)){
	    flg=1;
	    break;
	  }
	}
	if(flg) break;
      }
      if(flg) ans++;
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 65400
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
using namespace std;
using ll = long long;

int a[5010];
int dp[5010][5010];
map<int, int> mp;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
    int n; cin >> n;
    for(int i=0; i<n; ++i){
        cin >> a[i];
    }
    int ans=2;
    sort(a, a+n);
    for(int i=0; i<n; ++i){
        mp[a[i]]=i;
    }
    
    for(int i=0; i<n; ++i){
        for(int j=i+1; j<n; ++j){
            dp[i][j] = max(dp[i][j], 2);
            
            ans = max(ans, dp[i][j]);
            int k = a[j]+a[j]-a[i];
            
            if(mp.find(k)!=mp.end()){
                int idx = mp[k];
                dp[j][idx] = max(dp[j][idx], dp[i][j] + 1);
            }
        }
    }
    cout << ans << endl;
    
	return 0;

}


Measured memory_bytes: 70176
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
 
int main() {
    int n;
    ll a[200000];
    ll ans1=0;
    ll ans2=0;
    ll ans3=0;
    ll ans4=0;
    cin>>n;
    rep(i,n)    cin>>a[i];

    ll sum=0;

    rep(i,n) {
        sum+=a[i];
    }
    ll mid=sum/2;
    
    ll l=0;
    ll f=0;
    rep(i,n) {
        l+=a[i];
        if(l>mid) {
            f=l-a[i];
            break;
        }
    }
    ll fa=sum-f;
    ll la=sum-l;
    ll f2=f;
    ll fa2=fa;
    ll l2=l;
    ll la2=la;
    
    while(f!=fa) {
        f++;
        ans1++;
    }
    while(f2!=fa2) {
        fa2--;
        ans3++;
    }
    while(l!=la) {
        l--;
        ans2++;
    }
    while(l2!=la2) {
        la2++;
        ans4++;
    }

    cout<<min(ans1,min(ans2,min(ans3,ans4)))<<endl;
    
  
 return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n,p,nb = 0;
  cin >> n;
  for(ll i = 1; i <= n; ++i){
    cin >> p;
    if(p != i) ++nb;
  }
  if(nb <= 2) cout << "YES";
  else cout << "NO";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(i64 i = 0; i < (i64) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;
  vi P(A), Q(B), R(C);
  cin >> P >> Q >> R;
  sort(rrng(P));
  sort(rrng(Q));
  while(P.size()>X) P.pop_back();
  while(Q.size()>Y) Q.pop_back();

  vi con{P};
  for(auto &p : Q) con.emplace_back(p);
  for(auto &p : R) con.emplace_back(p);

  sort(rrng(con));
  cout << accumulate(con.begin(),con.begin()+X+Y,0LL) << endl;
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 6464
import java.util.Scanner;

/**
 * 素数判定
 * @author nobu
 * @see <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C&lang=ja">ALDS1_1_C</a>
 */
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int answer = 0;
		for (int i = 0; i < n; i++) {
			if (isPrime(sc.nextInt())) answer++;
		}

		System.out.println(answer);

		sc.close();
	}

	private static boolean isPrime(int x) {
		if (x == 2) return true;
		if (x < 2 || x % 2 == 0) return false;

		for (int i = 3; i <= Math.sqrt(x); i += 2) {
			if (x % i == 0) return false;
		}
		return true;
	}

}



Measured memory_bytes: 41216
function main(input) {
  input = input.trim().split("\n");
  const c = input.map(s => s.split(" ").map(t => Number(t)));
  let result = "No";
  const a1 = 0;
  const b1 = c[0][0] - a1;
  const a2 = c[1][0] - b1;
  const a3 = c[2][0] - b1;
  const b2 = c[0][1] - a1;
  const b3 = c[0][2] - a1;
  if (c[1][1] === a2 + b2 && c[1][2] === a2 + b3 && c[2][1] === a3 + b2 && c[2][2] === a3 + b3) {
    result = "Yes";
  }
  console.log(result);
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
const ll mod = 1e9+7;
long double PI = acosl(-1);
const ll infl = 1e15;
const int inf = 1e9;
const int nmax = 2e5+5;
const int MAXLG = log2(nmax)+1;
//mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;

int arr[nmax];

bool shobn(int n){
    for(int i=1; i<=n; i++) if(arr[i]!=n) return false;
    return true;
}

int sam[nmax];

void work(int n){
    memset(sam, 0, sizeof sam);
    for(int i=1; i<=n; i++){
        sam[ max(1, i-arr[i]) ]++;
        sam[ min(n, i+arr[i])+1 ]--;
    }
    for(int i=1; i<=n; i++) sam[i] += sam[i-1], arr[i] = sam[i];
}

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

    int n,k;
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>arr[i];

    while(k--){
        if(shobn(n)) break;
        work(n);
    }

    for(int i=1; i<=n; i++) cout<<arr[i]<<" ";

}
/*
*/


Measured memory_bytes: 5220
/**
**	author : Raghav
**	codechef:raghav_456
**	codeforces:raghavramola7
**/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define endl 			"\n"
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void Raghav()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(10);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
	Raghav();
	int k, n, a, sum = 0, i = 0;
	vector<int>v;
	cin >> n >> k;
	if (k >= n)
	{
		cout << 0;
		exit(0);
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> a;
		sum += a;
		v.pb(a);
	}
	sort(v.begin(), v.end(), greater<int>());
	while (k--)
	{
		sum -= v[i++];
	}
	cout << sum;

	return 0;
}

Measured memory_bytes: 5364
#include<bits/stdc++.h>
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-12)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

int n,m;
vector<pair<int,string> > v;
vector<string> u;

string solve(){
  sort(all(v));
  int index = 0, d = 0;
  FOR(i,0,m){
    if(index==n)return "No";
    FOR(j,index,n){
      if(v[j].s==u[i] && v[j].f!=d){
        index = j+1;
        d = v[j].f;
        break;
      }
      if(j==n-1)return "No";
    }
  }
//  cout<<n<<" "<<m<<endl;
//  cout<<v.size()<<" "<<u.size()<<endl;
  return "Yes";
}

int main()
{
  cin>>n;
  FOR(i,0,n){
    int c;
    string d;
    cin>>d>>c;
    v.pb(mp(c,d));
  }
  cin>>m;
  FOR(i,0,m){
    string s;
    cin>>s;
    u.pb(s);
  }
  cout<<solve()<<endl;
  return 0;
}



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

#define ll long long int
#define ld long double
#define pb push_back
#define pq priority_queue
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vvll vector<vector<ll>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define vll vector<ll>
#define MODNUM 1000000007
#define lp(i,a,b) for(ll i=a; i<b; i++)

using namespace std;

ll mex(ll a, ll b, ll m) {
	if(b==0) return 1;
	if(b%2) return a*mex((a*a)%m,(b-1)/2,m)%m;
	else return mex((a*a)%m,b/2,m);
}

int x,y;
void exteu(ll a, ll m) {
	if(m==0) { x=1;y=0; }
	else {
		exteu(m,a%m);
		ll temp = x;
		x=y;
		y=temp-(a/m)*y;
	}
}

ll fact(ll n) 
{	ll prod=1;
	for(ll i=2; i<=n; i++) {
		prod*=i;
	}
	return prod;
}

ll gcd(ll a, ll b) {
	if(b==0) return a;
	return gcd(b, a%b);
}
// 2 2 2 7
// 2 2 2 3 3
// 3 3 7

// 3
// 2 
// 3 3
bool isprime[200001];
void makesieve() {
	memset(isprime, true, sizeof(isprime));
	for (int i = 2; i <= sqrt(200000); ++i)
	{
		/* code */
		if(isprime[i]) {
			for (int j = i*i; j <= 200000; j+=i)
			{
				/* code */
				isprime[j]=false;
			}
		}
	}
}
// 1001100110011001
void solve() {
	ld a,b; cin>>a>>b;
	cout<<(ll)(a*b);
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll TESTS=1;
	// cin >> TESTS;
	// makesieve();
	while(TESTS--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3804
x, y, a, b, c = list(map(int, input().split()))
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
box = p[:x] + q[:y] + r
box.sort(reverse=True)
print(sum(box[:x+y]))


Measured memory_bytes: 22560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

VI G[100010];
int reached[100010];
int color[100010];


int main(){
    int n,d;cin>>n>>d;
    int x[n][d];
    int ans=0;
    rep(i,n) rep(j,d) cin>>x[i][j];
    rep(i,n) rep(j,i+1,n){
        double res=0;
        rep(k,d){
            res+=(x[i][k]-x[j][k])*(x[i][k]-x[j][k]);
        }
        double compare=floor(sqrt(res));
        if(compare*compare==res)ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560