akhauriyash/Code-Regression huggingface dataset:
#python3
def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    s = sum(a)
    x = s/(4*m)
    c = 0
    for i in range(n):
        if x > a[i]:
            c += 1
    
    k = n-c
    if k >= m:
        print('Yes')
    else:
        print('No')
main()


Measured memory_bytes: 3060
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    s = sum(A)
    if s<=N:
        print(N-s)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9988
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    p.sort()
    print(sum(p[:k]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


Measured memory_bytes: 62224
N = int(input())
W = list(map(int, input().split()))
         
s1 = 0
s2 = sum(W)
diff = s2
for i in range(N):
  s1 += W[i]
  s2 -= W[i]
  if abs(s1 - s2) < diff:
    diff = abs(s1 - s2)
print(diff)

Measured memory_bytes: 3060
#!/usr/bin/python

import sets
import sys

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent, parent[x])
        return parent[x]

def union(parent, x, y):
    parent_x = find(parent, x)
    parent_y = find(parent, y)

    if parent_x != parent_y:
        parent[parent_y] = parent[parent_x]

def main(argv):
    tokens = sys.stdin.readline().rstrip("\n").split()

    while len(tokens) == 3:
        n, k, l = [int(i) for i in tokens]

        parent_roads = [int(i) for i in xrange(n)]
        parent_railways = [int(i) for i in xrange(n)]

        for i in xrange(k):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_roads, x - 1, y - 1)

        for i in xrange(l):
            x, y = [int(i) for i in raw_input().split(" ")]
            union(parent_railways, x - 1, y - 1)

        count = dict()
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            if not count.has_key(key):
                count[key] = 0
            count[key] += 1

        results = []
        for i in xrange(n):
            key = (find(parent_roads, i), find(parent_railways, i))
            results.append(str(count[key]))
        print " ".join(results)

        tokens = sys.stdin.readline().rstrip("\n").split()

if __name__ == "__main__":
    main(sys.argv)

Measured memory_bytes: 49588
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
int dp[100005], n, h[100005], res;
int main() {
    DAU
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = n - 1; i; --i) {
        if (h[i+1] > h[i])
            dp[i] = 0;
        else dp[i] = dp[i+1] + 1;
        res = max(res, dp[i]);
    }
    cout << res;
    PLEC
}


Measured memory_bytes: 4376
#include<iostream>
using namespace std;
int main()
{
    string n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n.size();i++)
    {
        int a=n[i]-'0';
        sum=sum+a;
    }
    if(sum%9==0)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }

}


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

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    vector<ll> area(s.size()+1,0);
    vector<ll> hei(40000,1e9),wid(40000,1e9);


    ll maxh=20000,minh=400000;
    ll loch=20000;
    hei[20000]=0;
    for(ll i=1;i<=s.size();i++){
//        cout << s[i-1];
//        cout <<"loch : "<< loch << endl;
        if(s[i-1]=='\\'){
            loch--;
        }else if(s[i-1]=='/'){
            loch++;
            if(hei[loch]!=1e9){
                area[i]=(i-hei[loch]-1); //area
                wid[i]=hei[loch]; //start i of area
            }
        }
        hei[loch]=i;
    }
//    for(ll i=0;i<=s.size();i++){
//        cout << i;
//        cout << " area : "<< area[i];
//        cout << " begin wid : "<<wid[i] << endl;
//    }
//
    ll bw=0,cou=-1;
    stack<pair<ll,ll> > st;
    for(ll i=0;i<=s.size();i++){
        if(area[i]!=0){
            if(wid[i]>=bw){
                st.push(make_pair(i,area[i]));
                bw=wid[i];
            }else{
                for(;!st.empty();){
                    ll j=st.top().first;
                    ll a=st.top().second;
                    if(wid[j]>wid[i]){
                        area[i]+=a;
                        st.pop();
                    }else{
                        break;
                    }
                }
                st.push(make_pair(i,area[i]));
            }
        }
    }

    ll sumare=0;
    ll siz=st.size();
    vector<ll> vc;
    for(ll i=0;i<siz;i++){
        sumare += st.top().second;
        vc.push_back(st.top().second);
        st.pop();
    }

    cout << sumare << endl;
    cout << siz << (siz!=0?" ":"\n");
    for(ll i=vc.size()-1;i>=0;i--){
        cout << vc[i] << (i!=0?" ":"\n");
    }
}



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

using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<int>> A(H, vector<int>(W));
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      cin >> A[y][x];
    }
  }

  int M = 0;
  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      int B;
      cin >> B;
      A[y][x] -= B;
      A[y][x] = abs(A[y][x]);
      M = max(M, A[y][x]);
    }
  }

  const int MAX_K = (M + 1) * (H + W + 2);
  vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(MAX_K)));
  dp[0][0][A[0][0]] = true;

  for (int y = 0; y < H; y++) {
    for (int x = 0; x < W; x++) {
      int curr = A[y][x];
      if (y >= 1) {
        // come from up
        int px = x;
        int py = y - 1;
        for (int prev = 0; prev < MAX_K; prev++) {
	  if (!dp[py][px][prev]) continue;
          int sum0 = abs(curr + prev);
          if (sum0 < MAX_K) dp[y][x][sum0] = true;
          int sum1 = abs(curr - prev);
          if (sum0 < MAX_K) dp[y][x][sum1] = true;
        }
      }

      if (x >= 1) {
        // come from left
        int px = x - 1;
        int py = y;
        for (int prev = 0; prev < MAX_K; prev++) {
	  if (!dp[py][px][prev]) continue;
          int sum0 = abs(curr + prev);
          if (sum0 < MAX_K) dp[y][x][sum0] = true;
          int sum1 = abs(curr - prev);
          if (sum0 < MAX_K) dp[y][x][sum1] = true;
        }
      }
    }
  }

  for (int i = 0; i < MAX_K; i++) {
    if (dp[H - 1][W - 1][i]) {
      cout << i << endl;
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 11008
#include<bits/stdc++.h> 
using namespace std; 
   
int countFreq(string &pat, string &txt) 
{ 
    int M = pat.length(); 
    int N = txt.length(); 
    int res = 0; 
    
    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++) 
    {  
        /* For current index i, check for  
           pattern match */
        int j; 
        for (j = 0; j < M; j++) 
            if (txt[i+j] != pat[j]) 
                break; 
   
        // if pat[0...M-1] = txt[i, i+1, ...i+M-1] 
        if (j == M)   
        { 
           res++; 
           j = 0; 
        } 
    } 
    return res; 
} 
    
/* Driver program to test above function */
int main() 
{ 
  int n;
  cin>>n;
   string txt;
  cin>>txt;
   string pat = "ABC"; 
   cout << countFreq(pat, txt); 
   return 0; 
} 


Measured memory_bytes: 256
using System;

class Program {
    private static int Main() {
        var input = Console.ReadLine();
        var values = input.Split( ' ' );

        int a = int.Parse( values[ 0 ] );
        int b = int.Parse( values[ 1 ] );
        int c = int.Parse( values[ 2 ] );

        if( a > b ) {
            Swap( ref a, ref b );
        }
        if( b > c ) {
            Swap( ref b, ref c );
        }
        if( a > b ) {
            Swap( ref a, ref b );
        }


        var output = string.Format( "{0} {1} {2}", a, b, c );
        Console.WriteLine( output );

        return 0;
    }

    private static void Swap( ref int a, ref int b ) {
        var tmp = a;
        a = b;
        b = tmp;
    }
}

Measured memory_bytes: 5616
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <map>
#include <unordered_map>
#include <chrono>
#include <numeric>
using namespace std;
using ll = long long;
const long long INF = (long long)1e18+1;
#define DIV 1000000007
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef TEST
    chrono::system_clock::time_point start, end;
    start = chrono::system_clock::now();
#endif
    long idx=0;
    long N, K;
    cin >> N >> K;
    long R, S, P;
    cin >> R >> S >> P;
    string T;
    cin >> T;
    // R S P の数
    map<long,bool> R_index;
    map<long,bool> S_index;
    map<long,bool> P_index;
    for(size_t i=0;i<N; i++)
    {
        if(T[i] == 'r')
        {
            if(i-K >= 0 && R_index[i-K]) continue;
            R_index[i] = true;
        }
        else if(T[i] == 's')
        {
            if(i-K >= 0 && S_index[i-K]) continue;
            S_index[i] = true;
        }
        else
        {
            if(i-K >= 0 && P_index[i-K]) continue;
            P_index[i] = true;
        }
    }
    long R_count=0;
    for (const auto& elem : R_index){
        //cerr << "R:" << elem.first << ":" << elem.second << endl;
        if(elem.second) R_count++;
    }
    long S_count=0;
    for (const auto& elem : S_index){
        //cerr << "S:" << elem.first << ":" << elem.second << endl;
        if(elem.second) S_count++;
    }
    long P_count=0;
    for (const auto& elem : P_index){
        //cerr << "P:" << elem.first << ":" << elem.second << endl;
        if(elem.second) P_count++;
    }
    cout << R_count * P + S_count * R + P_count * S << endl;
#ifdef TEST
    end = chrono::system_clock::now();
    cerr << static_cast<double>(chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0) << "[ms]" << endl;
#endif
    return 0;
}

Measured memory_bytes: 12880
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int main()
{
    int H, W;
    cin>>H>>W;
    vector<vector<char>> s(H, vector<char>(W));
    for (int i=0;i<H;i++) {
        for (int j=0;j<W;j++) {
            cin>>s[i][j];
        }
    }
    int ans=0;
    for (int i=0;i<H;i++) {
        for (int j=0;j<W;j++) {
            if ('#'==s[i][j]) {
                continue;
            }
            queue<P> q;
            vector<vector<int>> dist(H+5, vector<int>(W+5, -1));
            dist[i][j]=0;
            vector<int> ver={ 0, -1, 0, 1 };
            vector<int> hor={ -1, 0, 1, 0 };
            q.push(make_pair(i, j));
            while (!q.empty()) {
                P temp=q.front();q.pop();
                for (int k=0;k<4;k++) {
                    int tempi=temp.first+ver[k];
                    int tempj=temp.second+hor[k];
                    if (tempi<0||tempi>=H||tempj<0||tempj>=W) {
                        continue;
                    }
                    if (s[tempi][tempj]!='.') {
                        continue;
                    }
                    if (dist[tempi][tempj]!=-1) {
                        continue;
                    }
                    q.emplace(tempi, tempj);
                    dist[tempi][tempj]=dist[temp.first][temp.second]+1;
                    ans=max(ans, dist[tempi][tempj]);
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3616
#include <cstdio>
#include <vector>
#include <climits>

int main() {
    int size = 0;
    std::vector<int> numList;

    scanf("%d", &size);

    numList.resize(size);

    for (size_t i = 0; i < numList.size(); ++i) {
        int num = 0;
        scanf("%d", &num);
        numList[i] = num;
    }

    int maxinumProfit = INT_MIN;
    int minv = numList[0];
    for (size_t i=1; i < numList.size(); ++i) {
        maxinumProfit = std::max(maxinumProfit, numList[i] - minv);
        minv = std::min(minv, numList[i]);
    }

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

    return 0;
}



Measured memory_bytes: 3188
def main():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    res = [0 for _ in range(N)]
    L = []
    for s, c in S:
        for ls, lc in L:
            if ls == s and lc != c:
                return -1
        if N != 1 and s == 1 and c == 0:
            return -1
        L.append([s, c])
        res[s - 1] = c
    if N != 1 and res[0] == 0:
        res[0] = 1

    return "".join(map(str, res))


print(main())


Measured memory_bytes: 38384
#include <stdio.h>
#include <stdlib.h>

int top = 0, S[100];

void push(int x)
{
	++top;
	S[top] = x;
}

int pop()
{
	--top;
	return S[top + 1];
}

int main(void)
{
	char s[1000];
	int a, b;
	while (scanf("%s", s) != EOF) {
		if (s[0] == '+') {
			a = pop();
			b = pop();
			push(a + b);
		}
		else if (s[0] == '-') {
			b = pop();
			a = pop();
			push(a - b);
		}
		else if (s[0] == '*') {
			a = pop();
			b = pop();
			push(a * b);
		}
		else push(atoi(s));
	}
	printf("%d\n", pop());
	return 0;
}


Measured memory_bytes: 2124
const main = input => {
  const [a, b, c] = input.trim().split(' ').map(x => parseInt(x))
  if (a + b === c || a + c === b || b + c === a) {
    console.log('Yes')
  } else {
    console.log('No')
  }
}

// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


Measured memory_bytes: 29420
#include<stdio.h>

int n ,A[100000];
int partition(int p,int r){
int j,x,i,t;
x = A[r];
i = p-1;
for(j=p;j<r;j++){
   
    if(A[j] <= x){
i++;

t=A[i];
A[i]=A[j];
A[j]=t;
    }

}

t=A[i+1];
A[i+1]=A[r];
A[r]=t;

return i+1;
}
int main(){
    int i,count=0,t;

scanf("%d",&n);

for(i = 0 ; i < n ; i++){

scanf("%d",&A[i]);

}
t = partition(0 ,n-1);


for(i = 0 ; i < t ; i++){

    printf("%d ",A[i]);
}
printf("[%d] ",A[t]);
count = t;
for(i=t+1;i<n;i++){
    count++;
printf("%d",A[i]);

if(count != n-1)
printf(" ");

}
printf("\n");

return 0;
}





Measured memory_bytes: 2244
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

typedef pair<int, int> pii;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

int maxSquare(vector< vector<int> > board) {
    int H = board.size(), W = board[0].size();
    vector< vector<int> > dp(H, vector<int>(W));

    int ret = 0;
    rep(i,0,H) rep(j,0,W) {
        if(board[i][j] == 1) continue;
        if(i == 0 || j == 0) dp[i][j] = 1;
        else {
            int mi = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]));
            dp[i][j] = mi + 1;
        }
        chmax(ret, dp[i][j] * dp[i][j]);
    }
    return ret;
}

signed main() {
    int H, W; cin >> H >> W;
    vector< vector<int> > board(H, vector<int>(W));
    rep(i,0,H) rep(j,0,W) cin >> board[i][j];
    cout << maxSquare(board) << endl;
    return 0;
}

Measured memory_bytes: 48972
// Last Change: 09/28/2019 22:29:20.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
  if (a == 0 and b == 0)
    return 0;
  a = abs(a);
  b = abs(b);
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}

int main() {
  ll A, B;
  cin >> A >> B;

  ll g = gcd(A, B);

  list<ll> furui;
  auto center = furui.begin();
  for (ll i = 2; i * i <= g; ++i) {
    if (g % i == 0) {
      center = furui.insert(center, i);
      ++center;
      if (i * i != g) {
        center = furui.insert(center, g / i);
      }
    }
  }
  furui.push_back(g);

  ll cnt = 1;
  if (furui.front() == 1) {
    furui.clear();
  }
  while (!furui.empty()) {
    ll val = furui.front();
    ++cnt;
    for (auto itr = furui.begin(); itr != furui.end();) {
      if (*itr % val == 0) {
        itr = furui.erase(itr);
      } else {
        ++itr;
      }
    }
  }
  cout << cnt << endl;
}


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

using namespace std;

int a[222222];
long b[222222];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", a + i), b[i + 1] = b[i] + a[i];
	long x = 1e18;
	int m = 1, i = 2, k = 3;
	while (i < n - 1) {
		long p = b[m], q = b[i] - b[m], r = b[k] - b[i], s = b[n] - b[k];
		if (abs(p - q) > abs(b[m + 1] - b[i] + b[m + 1])) {
			m++;
			continue;
		}
		if (abs(r - s) > abs(b[k + 1] - b[i] - b[n] + b[k + 1])) {
			k++;
			continue;
		}
		vector<long> v;
		v.push_back(p);
		v.push_back(q);
		v.push_back(r);
		v.push_back(s);
		sort(v.begin(), v.end());
		x = min(x, v.back() - v[0]);
		i++;
	}
	cout << x << endl;
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define mod ((ull)(1e9)+7)
#define MAX ((ull)(1e9)+1)

int main(){
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	cout << (h-a)*(w-b) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

//#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
  ll A, B;
  cin >> A >> B;
  if ((A+B)%2 == 0) {
      cout << (A+B)/2 << endl;
  } else {
      cout << "IMPOSSIBLE" << endl;
  }
}


Measured memory_bytes: 256
n = int(input())
a = []
m,a,r,c,h = 0,0,0,0,0

for i in range(n):
  s = input()
  if s[0] is 'M':
    m += 1
  if s[0] is 'A':
    a += 1
  if s[0] is 'R':
    r += 1
  if s[0] is 'C':
    c += 1
  if s[0] is 'H':
    h += 1
    
list = [m,a,r,c,h]

print(m*a*r + m*a*c + m*a*h + a*r*c + a*r*h + r*c*h + m*r*c + m*r*h + m*c*h + a*c*h)
  




Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,ans=0;
  cin>>N;
  unordered_map<int,int> M;
  for(int i=0;i<N;i++){
    int a;
    cin>>a;
    if(M[a]==0){M[a]=1;ans++;}
    else if(M[a]==1){M[a]=0;ans--;}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 7232
#[allow(dead_code)]
fn scan<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn scan_split<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|t| t.parse().ok().unwrap()).collect()
}

#[allow(dead_code)]
fn scan_split_with<T: std::str::FromStr>(ch: char) -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split(ch)
        .map(|t| t.parse().ok().unwrap()).collect()
}

#[allow(dead_code)]
fn scan_lines<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| scan::<T>()).collect()
}

#[allow(unused_macros)]
macro_rules! scan_as_tuple {
    ( $t:ty ) => {
        (scan::<$t>(),)
    };
    ( $( $t:ty ),* ) => {
        {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).ok();
            let v = s.trim().split_whitespace();
            let mut it = v;
            let ret = ( $(it.next().unwrap().parse::<$t>().ok().unwrap()),* );
            assert!(it.next() == None, "not all tokens consumed");
            ret
        }
    };
}

fn main() {
    let x = scan::<i32>();
    println!("{}", if x < 1200 { "ABC" } else { "ARC" });
}

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

int main()
{

string  S,T;
cin >> S;
cin >>T;
   
if (S==T){
cout<<3<<endl;
} 
    
else if ((S[0]==T[0] &&  S[1]!=T[1] && S[2]!=T[2]) ||
(S[0]!=T[0] && S[1]==T[1] && S[2]!=T[2] ) ||
(S[0]!=T[0] && S[1]!=T[1] && S[2]==T[2])){
cout <<1<<endl;
}
else if (S[0]!=T[0] && S[1]!=T[1] && S[2]!=T[2]){
cout <<0<<endl;
}
    
else{
cout <<2 << endl;    
}
    
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n = I()
XYH = TIR(n)
XYH.sort(key=itemgetter(2), reverse=True)
H = INF
CX = INF
CY = INF
for cx in range(100+1):
    for cy in range(100+1):
        tmp = INF
        for x, y, h in XYH:
            if tmp == INF:
                tmp = h+abs(x-cx)+abs(y-cy)
            elif h != max(tmp - abs(x-cx) - abs(y-cy), 0):
                break
        else:
            H = tmp
            CX = cx
            CY = cy
print("{} {} {}".format(CX, CY, H))


Measured memory_bytes: 66796
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,q;
    cin >> n >> q;
    vector<list<int>> L(n);
    while (q--) {
        int code;
        cin >> code;
        switch (code) {
            case 0: {
                int t,x;
                cin >> t >> x;
                L[t].push_back(x);
            } break;
            case 1: {
                int t;
                cin >> t;
                int m = L[t].size();
                int j = 0;
                if (m == 0) cout << endl;
                else 
                    for (auto i=L[t].begin();i!=L[t].end();i++,j++) {
                        cout << *i ;
                        if (j == m-1) cout << endl;
                        else cout << " ";
                    }
            } break;
            case 2: {
                int s,t;
                cin >> s >> t;
                L[t].splice(L[t].end(), move(L[s]));
                L[s].clear();
            } break;
        }
    }
}



Measured memory_bytes: 18712
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
const long double EPS = 1e-14;
const int maxn = 100500;
const int mod = 1e9 + 7;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector < int > a(n);
    for(auto &x : a) cin >> x;
    vector < int > v, st;
    for(int i = 0 ; i < n ; ++i){
        v.push_back(a[i]);
        if(a[i]){
            st.push_back(1);
            continue;
        }
        int j = i;
        while(j < n && !a[j]) ++j;
        st.push_back(j - i);
        i = j - 1;
    }
    int ans = 0;
    for(int i = 0 ; i < sz(v) ; ++i){
        int sm = v[i], xr = v[i];
        ans += st[i] * (st[i] + 1) / 2;
        for(int j = i + 1 ; j < min(sz(v), i + 50); ++j){
            sm += v[j];
            xr ^= v[j];
            ans += (sm == xr) * st[i] * st[j]; 
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 5220
import java.util.*;
public class Main{

 
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long ans = 1;
    for(int i = 1; i <= n; i++){
      ans = (ans * i) % 1000000007;
    }
 
    System.out.println(ans);
  }
}

Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
struct Vec2
{
	Vec2(){}
	Vec2(T _x, T _y) : x(_x), y(_y) {}

	Vec2 operator+(const Vec2& rhs) const { return Vec2(x + rhs.x, y + rhs.y); }
	Vec2 operator-(const Vec2& rhs) const { return Vec2(x - rhs.x, y - rhs.y); }
	Vec2 operator*(T s) const { return Vec2(x*s, y*s); }
	Vec2 operator/(T s) const { return Vec2(x/s, y/s); }
	T dot(const Vec2& rhs) const { return x*rhs.x + y*rhs.y; }
	T cross(const Vec2& rhs) const { return x*rhs.y - y*rhs.x; }
	T sqlength() const { return x*x + y*y; }
	double length() const { return sqrt(sqlength()); }
	bool operator<(const Vec2& rhs) const
	{
		if (x != rhs.x) return x < rhs.x;
		return y < rhs.y;
	}

	T x;
	T y;
};

template<class T>
T cross(const Vec2<T> &O, const Vec2<T> &A, const Vec2<T> &B)
{
	return (A - O).cross(B - O);
}

template<class T>
bool IsConvex(const vector<Vec2<T> >& poly)
{
	for (size_t i = 0; i < poly.size() - 2; i++) {
		if (cross(poly[i + 1], poly[i + 2],  poly[i]) < 0 ) {
			return false;
		}
	}
	return true;
}

int main()
{
	typedef Vec2<long long> Vec;

	int n;
	cin >> n;
	vector<Vec> poly(n);
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		poly[i] = Vec(x, y);
	}
	poly.push_back(poly[0]);
	poly.push_back(poly[1]);
	cout << IsConvex(poly) << endl;
	return 0;
}


Measured memory_bytes: 3120
# ALDS_5_A - 総当たり　
import sys

n = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
q = int(input())
m = list(map(int, sys.stdin.readline().strip().split()))

sum_set = set()

for i in range(2 ** n):
    bit = [(i >> j) & 1 for j in range(n)]
    combined = [x * y for (x, y) in zip(A, bit)]
    sum_set.add(sum(combined))

for target in m:
    if target in sum_set:
        print('yes')
    else:
        print('no')



Measured memory_bytes: 5656
#include <iostream>
#include <vector>


using namespace std;

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    int K;
    cin >> K;
    for (int i = 0; i < N; i++) {
        if (S[i] == S[K - 1])
            continue;
        else
            S[i] = '*';
    }
    cout << S << endl;

    return 0;
}

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

int main(){
  int n, m;
  cin >> n >> m;
  // ll ans = 0;
  unordered_map <int, int> ans;
  unordered_map <int, int> penalty;
  ll cnt = 0;
  ll penal = 0;
  for (int i = 0; i < m; i++){
    int p;
    string s;
    cin >> p >> s;
    if (s == "AC" && ans[p] == 0) {
      ans[p] = 1;
      penal += penalty[p];
    }
    if (s == "WA") penalty[p]++;
  }
  for (int i = 0; i < ans.size(); i++){
    if (ans[i] == 1) cnt++;
  }
  cout << cnt << ' ' << penal << endl;
}

Measured memory_bytes: 8520
#include<stdio.h>

int main(){
	long long x;
	scanf("%lld",&x);
	int count = 0;
	long long a = 100;
	while(a < x){
		a = a + (a/100);
		
		count++;
	}
	printf("%d",count);
	
	
	return 0;
}

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

int main() {
  int N;
  int a,b,c,d;
  a = 1;
  c = 0;
  cin >> N;
    a = a * 10;
    b = N % a;
    d = b;
    c = c + b;
   for (int i=0;i < 8;i++){
    a = a * 10;
    b = N % a;
    b = (b - d) / (a / 10);
    c = c + b; 
    d = b;
    
     }
  if (N % c == 0){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
    
}


Measured memory_bytes: 3560
n = gets.to_i
a = Array.new(n)
b = Array.new(n+1)
n.times do |i|
  a[i] =  gets.to_i
  b[a[i]] = i
end
max_len = 0

prev = 0

for i in 1..(n-1) do
  if b[i] < b[i+1]
    #prev = 1 if prev < 1
  else
    max_len = i - prev if i - prev > max_len #&& prev > 0
    prev = i
  end
end
max_len = n - prev if n - prev > max_len

puts n - max_len

Measured memory_bytes: 5244
a, b, k = map(int, input().split())
def gcd(a, b):
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)

g = gcd(a, b)
n = 0
for i in range(g, 0, -1):
  if g % i == 0:
    n += 1
  if n == k:
    print(i)
    quit()

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

using namespace std;
int main()
{
    int k;
    string s;
    cin >> k >> s;
    if(k<s.length()){
        int i = 0;
        while(i<k){
            cout << s[i];
            i++;
        }
        cout << "...";
    }
    else{
        cout << s;
    }
}

Measured memory_bytes: 3624
require 'prime'
n = gets.to_i
a = n.prime_division
aa = a.size
ans = 0
(0...aa).each do |i|
    s = a[i][1]
    x = 1
    s -= x
    while s >= 0
        ans += 1
        x += 1
        s -= x
    end
end

puts ans



Measured memory_bytes: 14412
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define sll set<ll>
#define str string
#define rev reverse
#define mp make_pair
#define pb push_back
#define acc accumulate
#define vll vector<ll>
#define eb emplace_back
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll> >
#define dq deque<ll>
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back

void knapSack(ll W, ll wt[], ll val[], ll n) 
{ 
   ll i, w; 
   ll K[n+1][W+1];
   for (i = 0; i <= n; i++) 
   { 
       for (w = 0; w <= W; w++) 
       { 
           if (i==0 || w==0) 
               K[i][w] = 0; 
           else if (wt[i-1] <= w) 
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
           else
                 K[i][w] = K[i-1][w]; 
       } 
   }
   cout <<  K[n][W] << endl; 
}

void solve()
{
    ll n,w,i,p,q,j;
    cin >> n >> w;
    ll val[n],wt[n];
    for(i=0;i<n;i++)
    {
        cin >> wt[i] >> val[i];
    }
    knapSack(w,wt,val,n);
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll cases;
    //cin >> cases;
    cases=1;
    for(ll i=0;i<cases;i++)
        solve();

    return 0;
}

Measured memory_bytes: 79232
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <set>
#include <string>
#include <tuple>

int main() {
  size_t N, M;
  scanf("%zu %zu", &N, &M);

  std::vector<intmax_t> A(N);
  for (auto& ai: A) scanf("%jd", &ai);

  std::vector<std::pair<intmax_t, size_t>> CB(M);
  for (auto& cbi: CB) {
    scanf("%zu %jd", &cbi.second, &cbi.first);
  }

  std::sort(A.begin(), A.end());
  std::sort(CB.begin(), CB.end());

  size_t i = 0;
  while (!CB.empty() && i < N) {
    intmax_t c = CB.back().first;
    
    if (A[i] > c) break;
    // fprintf(stderr, "%jd <- %jd\n", A[i], c);
    A[i++] = c;
    if (--CB.back().second == 0) CB.pop_back();
  }

  intmax_t res = std::accumulate(A.begin(), A.end(), 0LL);
  printf("%jd\n", res);
}


Measured memory_bytes: 2560
using System;
using System.Linq;
public class c
{
  public static void Main()
  {
    int N = int.Parse(Console.ReadLine());
    int sum=0;
    int i;
    for(i=0;i<N;i++)
    {
      int[] x=Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
      sum+=(x[1]-x[0]+1);
    }
    Console.WriteLine(sum);
  }
}

Measured memory_bytes: 11348
#include<iostream>
using namespace std;
int A;
int B;
int ans;
int main(){
  cin >> A;
  cin >> B;
  if(A>=13){
    ans=B;
  }
  if(A<=12){
    if(A>=6){
      ans=B/2;
    }
    if(A<=5){
    ans=0;
    }
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
#include<map>//map
using namespace std;
typedef long long LL; 
typedef pair<LL,LL> P;//Pでpair<-,->を表す。
const LL MAX=2000010;
const LL MOD=1000000007;
typedef map<LL,LL>::iterator Itr;

int main()
{ 
    int k;
    cin>>k;
    string s;
    cin>>s;
    if(s.size()<=k){cout<<s<<endl;}
    else{s=s.substr(0,k)+"...";cout<<s<<endl;}
    return 0;
}

Measured memory_bytes: 3628
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

(deftype int32 () '(signed-byte 32))
(deftype int64 () '(signed-byte 64))


;;macros
(defmacro println (n)
  `(format t "~a~%" ,n))
(defmacro vint-out (vec)
  `(progn
     (rep i (length ,vec)
          (princ (vref ,vec i))
          (princ " "))
     (fresh-line)))
(defmacro aif (test-form then-form &optional else-form)
  `(let ((it ,test-form))
     (if it ,then-form ,else-form)))

;;vector
(defmacro vec (type &optional (num 100) (val 0))
  (let* ((g (gensym)))
    `(let* ((,g ,num))
       (make-array ,g :element-type ',type :initial-element ,val
                   :adjustable nil :fill-pointer ,g))))

(defmacro double-vec (type &optional (dim1 100) (dim2 100) (val 0))
  `(make-array '(,dim1 ,dim2) :element-type ',type :initial-element ,val))

(defmacro vint (&optional (num 0) (val 0))
  `(vec int32 ,num ,val))

(defmacro double-vec (type &optional (dim1 100) (dim2 100) (val 0))
  `(make-array '(,dim1 ,dim2) :element-type ',type :initial-element ,val))

(defmacro vref (vector pos &optional value)
  (let ((g (gensym)))
    `(let ((,g ,value))
       (if ,g
           (setf (aref ,vector ,pos) ,g)
           (aref ,vector ,pos)))))

(defmacro chvar (sym comp predicate)
  (let ((g (gensym)))
    `(let ((,g ,comp))
       (if (or (null ,sym) (not (funcall ,predicate ,sym ,g)))
           (setf ,sym ,g)))))

(defmacro chmax (sym comp &optional (predicate #'>))
  `(chvar ,sym ,comp ,predicate))

(defmacro chmin (sym comp &optional (predicate #'<))
  `(chvar ,sym ,comp ,predicate))

(defmacro defchangef (name op default-val)
  `(defmacro ,name (var &optional (val ,default-val))
     `(setq ,var (,',op ,val ,var))))
(defmacro read-str ()
  `(write-to-string (read)))
(defmacro print-float (r)
  `(format t "~,9F~%" (coerce ,r 'double-float)))


;;本体

(defun main ()
  (let ((s (make-string 4)))
    (dotimes (i 4)
      (setf (aref s i) (read-char)))
    (println
     (if (or (char= (aref s 0) (aref s 1))
             (char= (aref s 1) (aref s 2))
             (char= (aref s 2) (aref s 3)))
          "Bad" "Good"))))



#-swank(main)


Measured memory_bytes: 21860
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.D
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var A = ReadLongs().OrderByDescending(x => x).ToList();
            var kokotiSum = 0L;
            for (var i = 0; i < N - 1; i++)
            {
                if (i == 0)
                {
                    kokotiSum += A[0];
                    continue;
                }
                if(i %2 == 0)
                {
                    kokotiSum += A[i / 2];
                }
                else
                {
                    kokotiSum += A[(i + 1) / 2];
                }
            }
            return kokotiSum;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 52900
n = int(input())
a = list(map(int, input().split()))
b = set()
for i in range(n - 1, -1, -1):
    count = 0
    c = i + 1
    while c < 200000:
        if c in b:
            count += 1
        c += (i + 1)
    if count % 2 != a[i]:
        b.add(i + 1)
print(len(b))
print(" ".join(list(map(str, b))))

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

typedef long long ll;
typedef vector<int> vi;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,n) FOR(i,0,n)
#define OUT(x) cout<<(x)<<"\n";

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main(){
    int n,k,l;
    cin >> n >> k >> l;
    UnionFind uf1(n), uf2(n);
    rep(i,k){
        int p, q;
        cin>>p>>q;
        --p; --q;
        uf1.unionSet(p,q);
    }
    rep(i,l){
        int p, q;
        cin>>p>>q;
        --p; --q;
        uf2.unionSet(p,q);
    }

    map<pair<int,int>, int> cnt;
    rep(i,n){
        ++cnt[make_pair(uf1.root(i), uf2.root(i))];
    }

    rep(i,n){
        cout << cnt[make_pair(uf1.root(i), uf2.root(i))];
        if(i != n-1) cout<<" ";
    }
    puts("");

    return 0;
}

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

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;
}
struct Unionfind {
    vector<int> par;
    vector<int> sizes;

    Unionfind(int n) : par(n), sizes(n, 1) {
        for(int i = 0; i < n; ++i) par[i] = i;
    }

    int root(int x) {
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        if(sizes[x] < sizes[y]) swap(x, y);
        par[ry] = rx;
        sizes[rx] += sizes[ry];
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) {
        return sizes[root(x)];
    }

};

const int MOD = 1e9+7;

ll modpow(int x, int times) {
    ll res = 1;
    for(int i = 0; i < times; ++i) {
        res = (res * x) % MOD;
    }
    return res;
}

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

    int n;
    cin >> n;

    ll ans = modpow(10, n) - modpow(9, n) - modpow(9, n) + modpow(8, n);

    while(ans < 0) ans += MOD;
    ans %= MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
#include<ctype.h>
# define pb push_back
#define fst first
#define sec second
#define For(i,a,b) for(int i=a;i<b;i++)
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define fo(i,n) for(ll i=0;i<n;i++)
#define endl "\n"
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define boolsize 1000001
#define pi pair<ll,ll>
#define vi vector<ll>
#define vii vector<pi>
using namespace std;
template<typename T>
void showvector(vector <T> v)
{
    for(T x:v)
        cout<<x<<" ";
    cout<<endl;

}
template<typename T>
void showvector1(vector <T> v)
{
    ll n=v.size();
    fo1(i,n-1)
        cout<<v[i]<<endl;

}
template<typename T>
void showset(set <T> s)
{
    for(T x: s)
        cout<<x<<" ";
    cout<<endl;
}
template<class T>
void showvectorpair(vector<T> v)
{
    for(auto it=v.begin();it!=v.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T,typename P>
void showmap(map <T,P> m)
{
    for(auto it=m.begin();it!=m.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T>
bool comp(T a,T b)
{
    return (a>b);
}
template<class T>
bool comppair(T a,T b)
{
    if(a.first==b.first)
        return(a.second>b.second);
    return (a.first>b.first);
}
bool sameparity(ll a,ll b)
{
    return (a%2==b%2);
}
bool difparity(ll a,ll b)
{
    return !(a%2==b%2);
}
bool isprime(ll x)
{   if(x<=1)
     return false;
    for(ll i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
bool iseven(ll x)
{
    return !(x%2);
}
bool isodd(ll x)
{
    return (x%2);
}
//vector <bool> prime(boolsize,1);
//void seive()
//{
//    ll n=boolsize;
//    prime[0]=prime[1]=0;
//    for(ll i=2;i<=sqrt(boolsize);i++)
//    {
//        if(prime[i]==1)
//        {
//            for(ll j=i*i;j<=n;j+=i)
//            {
//                prime[j]=0;
//            }
//        }
//    }
//}

/// check for test case before submitting
void vfun()
{
    ll n;
    cin>>n;
    vi v(n+1);
    fo1(i,n)
    {
            cin>>v[i];
    }
    ll cnt=0,x=1;
    ll i=0;
    for(i=1;i<=n;i++)
    {
        if(x==2)
            break;
        else
            x=v[x];
        cnt++;
    }
    if(i>n)
        cout<<"-1\n";
    else
        cout<<cnt;

}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); ///cant use scanf, printf
    cin.tie(0);cout.tie(0); /// no longer auto flush cout before each cin, remove for interactive
    //cout << fixed << setprecision(11); /// no scientific output
    ll test=1;
    //cin>>test;
    while(test--)
    {

        //fun();
        vfun();
//         if(vfun())
//            cout<<"YES\n";
//         else
//            cout<<"NO\n";
    }
}
///before sub
/// check for value of zero and single input in array
///loop vars,1LL in mult, equal, one, bounds, int v ll, endl, finish taking inputs
/// check whether test cases are given or not




Measured memory_bytes: 3980
def drop(lst,h,w):
    for i in range(w-1,-1,-1):
        work=[lst[j][i] for j in range(h)]
        work=[x for x in work if x]
        for j in range(h-1,-1,-1):
            if work: lst[j][i]=work.pop()
            else : lst[j][i]=None

def chain(lst,h,w,k):
    sm=0
    for j in range(h):
        train=1
        for i in range(w-1):
            if not lst[j][i] :
                train=1
                continue
            if lst[j][i]==lst[j][i+1]:
                train+=1
            else :
                if train>=k:
                    sm+=lst[j][i]*train
                    lst[j][i-train+1:i+1]=[None]*train
                train=1
        if train>=k:
            sm+=lst[j][-1]*train
            lst[j][-train:]=[None]*train
    return sm


def procedure(lst,h,w,k,x):
    lst[x[0]][x[1]]=None
    drop(lst,h,w)
    sm=0
    i=0
    point=chain(lst,h,w,k)
    while point:
        sm+=(2**i)*point
        drop(lst,h,w)
        point=chain(lst,h,w,k)
        i+=1
        #print(lst)
    return sm


def main():
    h,w,k=map(int,input().split())
    lst=[[int(x) for x in input()] for _ in range(h)]
    mx=0

    for i in range(1,h):
        for j in range(w):
            work=[[lst[i][j] for j in range(w)] for i in range(h)]
            sm=procedure(work,h,w,k,(i,j))
            if mx<sm : mx=sm
    print(mx)


main()

Measured memory_bytes: 70384
N = int(input())
Blist = list(map(int,input().split()))
ans = Blist[0]

for i in range(0,N-1):
    if i + 1 <N-1:
        if Blist[i] < Blist[i+1]:
            ans = ans + Blist[i]
        else:
            ans = ans + Blist[i+1]
    else:
        ans = ans + Blist[i]
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <algorithm>

using namespace std;

static const int MAX = 50;

int n;
int A[MAX];

int main(int argc, const char * argv[]) {
    
    /////////
    //write//
    /////////
    
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> A[i];
    }
    sort(A, A+n);
    double res = A[0];
    for(int i=0; i<n-1; i++){
        res = (res+A[i+1])/2;
    }
    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 256
A, B = map(int, input().split())
ans1 = int(A *100// 8) 
ans2 = int(B *100 // 10)
ans1_2 = int((A+1) *100 // 8)
ans2_2 = int((B+1) *100 // 10)
list1 = []
list2 = []

for i in range(ans1,ans1_2):
    if int(i * 0.08) == A: 
        list1.append(int(i))
for j in range(ans2,ans2_2):
    if int(j * 0.1) == B:
        list2.append(int(j))
if list1[0] == list2[0]:
    print(list1[0])
elif list1[0] > list2[0]:
    if list1[0] in list2:
        print(list1[0])
    else:
        print(-1)
elif list1[0] < list2[0]:
    if list2[0] in list1:
        print(list2[0])
    else:
        print(-1)
        

Measured memory_bytes: 3064
#include<cstdio>
using namespace std;
typedef long long int ll;

ll N, K;

int main(){
	scanf("%lld %lld", &N, &K);
	ll res = (N / K) * (N / K) * (N / K);
	if(K % 2 == 0){
		ll cnt = 0;
		for(int i = 1; i <= N; i++){
			if(i % K == K / 2) cnt++;
		}
		res += cnt * cnt * cnt;
	}
	printf("%lld\n", res);
	return 0;
}


Measured memory_bytes: 128
/*
Author: Arham_doshi
@quote "Code like there's no tommorow!"
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
#include <bits/stdc++.h>

#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define bs(v,n)     binary_search(all((v)),(n))
#define lb(v,n)     lower_bound(all((v)),(n))
#define ub(v,n)     upper_bound(all((v)),(n))
#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)
#define _init(b)     memset(b,-1,sizeof(b))
#define _init0(b)     memset(b,0,sizeof(b))
#define MOD         1000000007



using namespace std;

int gcd(int a, int b) {  if (a == 0)  return b; return gcd(b % a, a); }  
bool mod(double a,double b) {return a/b - floor(a/b);}

int occurs(vi v,int n){
auto it=lb(v,n);auto it1=ub(v,n);int x=it1-it;return x;}

int logb(int base, int x) {
    return (log(x) / log(base));
}



signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int i,j,x,t,n,k;
    cin>>n;
    bool p=false;
    fo(i,1,10){
        if(n%i==0){
            if(n/i<10)p=true;
        }
    }
    if(p)cout<<"Yes";
    else cout<<"No";
    
    return 0;
}

Measured memory_bytes: 256