akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
n = int(input())
a = list(map(int,input().split()))
a.append(0)
total = 0
for i in range(n+1):
    total += abs(a[i] - a[i-1])
    #print(total,abs(a[i] - a[i-1]))
for i in range(-1,n-1):
    if (a[i+1]-a[i]) *(a[i+2]-a[i+1]) > 0:
        print(total) # 間に挟まれるなら 
    else: print(total - 2 * min(abs(a[i+1] -a[i]) ,abs(a[i+1] -a[i+2])))


Measured memory_bytes: 14048
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)n; i++)
#define PI 3.14159265358979323846
#define vll vector<long long>
#define vvll vector<vector<long long>>
using namespace std;
using ll = long long;
using ld = long double;

// ----本問について----
// 問題：全点対間最短経路
// 問題文URL：https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_C
// 所要時間：1時間
// 学んだこと：
//  負辺を含む場合の扱い．INFの値が小さすぎて一回WAした．
//  テキストに「辺 ik と kj の存在を条件に加えること」とありましたが，辺ではなくて経路ではないでしょうか？
//  辺という言葉に経路という意味が含有されていたら申し訳ありません．
// ------------------

// ----ここから本問のソースコード----
const ll INF = 100100100100000;
const ll V_MAX = 110;

// グローバル変数（入力）
ll v, D[V_MAX][V_MAX];

void init() {
  rep(i, V_MAX) {
    rep(j, V_MAX) {
      if (i != j) {
        D[i][j] = INF;
      } else {
        D[i][j] = 0;
      }
    }
  }
}

// Dを出力する
void printD() {
  rep(i, v) {
    rep(j, v) {
      if (D[i][j] == INF) {
        cout << "INF";
      } else {
        cout << D[i][j];
      }
      if (j != v - 1) {
        cout << " ";
      } else {
        cout << endl;
      }
    }
  }
}

// 入力
void input() {
  cin >> v;
  ll e;
  cin >> e;
  init();
  rep(i, e) {
    ll s, t, d;
    cin >> s >> t >> d;
    D[s][t] = d;
  }
}

void solve() {
  // ワーシャルフロイド
  rep(k, v) {
    rep(i, v) {
      rep(j, v) {
        if (D[i][k] != INF && D[k][j] != INF) {
          D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
        }
      }
    }
  }

  // 負の閉路判定
  bool NC = false; // NegativeCycle
  rep(i, v) {
    if (D[i][i] < 0) {
      NC = true;
      break;
    }
  }
  if (NC) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    printD();
  }
}

int main() {
  input();
  solve();
  return 0;
}



Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T, typename U, typename V>
ostream &operator<<(ostream &os, const tuple<T, U, V> &t){
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
  }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
string substr(const string &str, int S1, int S2 = -1){
  if(S2 == -1)return str.substr(S1);
  return str.substr(S1, S2-S1);
}
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef tuple<int, int, int> TT;
typedef pair<int, TT> PT;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);


int solve(vector<int> vec, int cnt){
  sort(all(vec));
  int mx = min(cnt, (int)vec.size());
  int ans = accumulate(all(vec), 0LL);
  // cout << vec << " " << ans << endl;
  rep(i,mx)if(vec[i] < 0)ans -= vec[i];
  return ans;
}

signed main(){
  int n, k;cin >> n >> k;
  vector<int> a(n);
  rep(i,n)cin >> a[i];
  
  int ans = 0;
  rep(i,n)for(int j = -1;j < n;j++){
    if(j < i-1)continue;
    vector<int> vec;
    rep(k,n){if(k < i or j < k)vec.pb(a[k]);}
    int cnt = vec.size();
    if(cnt > k)continue;
    ans = max(ans, solve(vec, k-cnt));
  }
  cout << ans << endl;
  return 0;
}






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

using namespace std;

int main() {
	int N, M, L, D;
	cin >> N >> M >> L >> D;
	if (((M-L<=D&& L - M <= D) && (N-M <=D&&M - N <= D))||(L-N<=D && N-L<=D)) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
}

Measured memory_bytes: 888
/*          _           __                _      _____ _____ _____ 
  ___ _   _| |__   ___ / _|_ __ ___  __ _| | __ |___  |___  |___  |
 / __| | | | '_ \ / _ \ |_| '__/ _ \/ _` | |/ /    / /   / /   / / 
| (__| |_| | |_) |  __/  _| | |  __/ (_| |   <    / /   / /   / /  
 \___|\__,_|_.__/ \___|_| |_|  \___|\__,_|_|\_\  /_/   /_/   /_/   

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vi;
typedef vector<pll> vpll;
typedef unordered_map <ll,ll> umap ; 
//#pragma GCC optimize "trapv"
#define loop(i,a,b) for(ll i=a ;i<b;i++)
#define For(i,n) for(int i=0;i<(ll)n;i++)
#define Rev(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,n) for(int i=1;i<=n;++i)
#define F first
#define S second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define mems(x, y) memset(x, y, sizeof(x))
#define sz(v) (v).size()
#define mp(a,b) make_pair(a,b)
#define pf(n) cout<<n<<endl;
#define pff(n) cout << n << " " ; 
long const M=1e9+7;
const long mxN =1e5+2  ;
const long mxNN =1e6+2 ;
ll wt[mxN],v[mxN],dp[100][mxN] ;  
void solve(){
     ll n,w; cin >> n >> w ;
     For(i,n)cin >>wt[i] >> v[i] ;
     For(i,n){
          For(j,w+1){
               if(j==0){
                    dp[i][j]=0 ;
                    continue ;
               }
               if(i==0){
                    dp[i][j]=(j>=wt[i]?v[i]:0) ;
                    continue ;
               }
               ll k = (j>=wt[i]?dp[i-1][j-wt[i]]+v[i]:INT_MIN) ;
               dp[i][j]=max(dp[i-1][j],k) ;
          }
     }
     // For(i,n){
     //      For(j,w+1){
     //           cout << dp[i][j] <<" " ;
     //      }
     //      cout << endl ;
     // }
     // backtracking the values 
    // vi value,weight ;ll curr_row=n-1,curr_col=w ;
    // while(curr_row>0){
    //       if(dp[curr_row-1][curr_col]==dp[curr_row][curr_col])curr_row-- ;
    //       else{
    //           // cout << curr_row <<endl ;
    //           value.pb(v[curr_row]);weight.pb(wt[curr_row]) ;
    //           curr_col-=(wt[curr_row]-1) ;curr_row-- ;
    //       }
    // }
    // for(auto x :value)cout << x << " " ;
    // cout << endl  ;
    // for(auto x :weight)cout << x << " " ;
     
     cout << dp[n-1][w] << endl ;
     
    
}

int main() {
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     solve() ;
     //ll t ; cin >> t ; while(t--)solve();
	return 0;
}


Measured memory_bytes: 81776
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <ctype.h>
#include <stdlib.h>
using namespace std;

int main() {
	int H, N;
	cin >> H >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)
	{
		cin >> A[i];
		H -= A[i];
	}

	if (H > 0) {
		cout << "No" << endl;
	}
	else {
		cout << "Yes" << endl;
	}


}


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

int main(){
  int n;
  cin >> n;
  int ans = 0;
  int mini = 1000000;
  int p[n];
  for(int i = 0; i < n; i++){
    cin >> p[i];
  }
  for(int i = 0; i < n; i++){
    if(p[i] < mini){
      ans++;
      mini = p[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
#define endl '\n'
using namespace std;
int dy[4] = {1,0,-1,0},dx[4] = {0,1,0,-1};
typedef pair<ll, ll> P;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int v[50], c[50];
    rep(i, n) { cin >> v[i]; }
    rep(i, n) { cin >> c[i]; }
    int ans = 0;
    rep(i, n) {
        if (v[i] > c[i]) {
            ans += v[i] - c[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in Actual solution is at the top
 *
 * @author dauom
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    BMinorChange solver = new BMinorChange();
    solver.solve(1, in, out);
    out.close();
  }

  static class BMinorChange {
    public final void solve(int testNumber, InputReader in, PrintWriter out) {
      char[] s = in.nextCharArray();
      char[] t = in.nextCharArray();
      int ans = 0;
      for (int i = 0; i < s.length; i++) {
        if (s[i] != t[i]) {
          ++ans;
        }
      }
      out.println(ans);
    }
  }

  static final class InputReader {
    private final InputStream stream;
    private final byte[] buf = new byte[1 << 16];
    private int curChar;
    private int numChars;

    public InputReader() {
      this.stream = System.in;
    }

    public InputReader(final InputStream stream) {
      this.stream = stream;
    }

    private final int read() {
      if (this.numChars == -1) {
        throw new UnknownError();
      } else {
        if (this.curChar >= this.numChars) {
          this.curChar = 0;

          try {
            this.numChars = this.stream.read(this.buf);
          } catch (IOException ex) {
            throw new InputMismatchException();
          }

          if (this.numChars <= 0) {
            return -1;
          }
        }

        return this.buf[this.curChar++];
      }
    }

    public final String next() {
      int c;
      while (isSpaceChar(c = this.read())) {}

      StringBuilder result = new StringBuilder();
      result.appendCodePoint(c);

      while (!isSpaceChar(c = this.read())) {
        result.appendCodePoint(c);
      }

      return result.toString();
    }

    private static final boolean isSpaceChar(final int c) {
      return c == 32 || c == 10 || c == 13 || c == 9
          || c == -1; // 32 == ' ', 10 == '\n', 13 == '\r', 9 == '\t'
    }

    public final char[] nextCharArray() {
      return next().toCharArray();
    }
  }
}


Measured memory_bytes: 36276
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder06
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] z = Console.ReadLine().Split(' ');
            int a = int.Parse(z[0]);
            int b = int.Parse(z[1]);
            int c = int.Parse(z[2]);

            Console.WriteLine(a*b/2);
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
#define qrep(que, ite) for(auto ite=begin(que) ; ite!=end(que) ; ite++)
const int max_n = 1e5;
const ll mod = 1e9+7;
const ll INF = 1e17;
const int inf = 1e5;
//typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
ll mo = 998244353;
struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }

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

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
struct SegmentTree{
  int N;
  vector<int> node;
  public :
    void intit(vector<int>v){
      int sz = v.size();
      N=1;
      while(N<sz) N*=2;
      node.resize(N);
      for(int i=0 ; i<sz ; i++) node[i+N-1] = v[i];
      for(int i=N-2 ; i>=0 ; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }
    void update(int x, int val){
      x += N-1;
      node[x+N-1] = val;
      while(x>0){
        x = (x-1)/2;
        node[x] = min(node[x*2+1], node[x*2+2]);
      }
    }
    int getmin(int a, int b, int k, int l, int r){
      if(b<=l || r<=a) return inf;
      else if(a<=l && r<=b) return node[k];
      else{
        int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
      }
    }
};

int main(){
  int N,M;  cin>>N>>M;
  vector<int> v(M);
  ll sum = 0;
  rep(i,0,M) cin>>v[i], sum+=v[i];
  if(sum>N)cout<<-1<<endl;
  else{
    cout<<N-sum<<endl;
  }
  return 0;
}


Measured memory_bytes: 3636
N,A,B = map(int,input().split())

B_max = B*(N-1)+A
A_min = A*(N-1)+B

if A>B:
  print(0)
elif A==B:
  print(1)
elif N==1:
  print(0)
else:
  print(B_max-A_min+1)

Measured memory_bytes: 38384
"""
input(): 入力を文字列として1行取ってくる
"文字列".split(): 文字列をパースする（空白などで分割する）
    例："2 3 4 5"　をsplitしたら、[2, 3, 4, 5] に分割する
map(型, list): list の中身をそれぞれ指定した型で変数に入れる
"""
N, M = map(int, input().split())

if N == M:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9056
#include<stdio.h>

int main(){

  int n,p,i,o,k;
  char str[16];

  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      o=0;
      p=0;
      k=0;
      while(o<3)
	{
	  scanf("%s",str);
	  if(str[1]=='U')
	     o++;
	  else if(str[1]=='O')
	       {
		 p=p+1+k%4;
		 k=0;
	       }
	  else if(str[1]=='I')
	       {
		 k++;
		 if(k%4==0)
		   {
		     p++;
		     k--;
		   }
	       }
	}
      printf("%d\n",p);
    }
  return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 110
#define ll long long
using namespace std;
int n,con[N],nxt[N<<1],to[N<<1],tote,dep[N],key,ans1,f[N];
ll ans2;
void ins(int x,int y)
{
	to[++tote]=y;nxt[tote]=con[x];con[x]=tote;
}
void dfs(int v,int fa,int &mxr)
{
	dep[v]=dep[fa]+1;
	mxr=max(mxr,dep[v]);
	int cnt=0;
	for(int p=con[v];p;p=nxt[p])
		if(to[p]!=fa&&(p>>1)!=key)
			dfs(to[p],v,mxr),cnt++;
	f[dep[v]]=max(f[dep[v]],cnt);
}
int main()
{
	scanf("%d",&n);
	tote=1;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	ans1=n;ans2=1e18;
	for(int i=1;i<=n;i++)
	{
		memset(dep,0,sizeof(dep));
		memset(f,0,sizeof(f));
		int mx=0;
		dfs(i,0,mx);
		ll tot=1;
		for(int j=1;j<mx;j++)
			tot*=f[j];
		if(mx<ans1) ans1=mx,ans2=1e18;
		if(mx==ans1) ans2=min(ans2,tot); 	
		//cout<<i<<' '<<mx<<' '<<tot<<endl;
	}
	for(int i=1;i<n;i++)
	{
		int x=to[i<<1],y=to[i<<1|1],mxx=0,mxy=0;
		memset(dep,0,sizeof(dep));
		memset(f,0,sizeof(f));
		key=i;
		dfs(x,0,mxx);
		dfs(y,0,mxy); 
		ll tot=2;
		int mx=max(mxx,mxy);
		for(int j=1;j<mx;j++)
			tot*=f[j];
		if(mx<ans1) ans1=mx,ans2=1e18;
		if(mx==ans1) ans2=min(ans2,tot);
				//cout<<x<<' '<<y<<' '<<' '<<mx<<' '<<tot<<endl;
	
	}
	printf("%d %lld",ans1,ans2);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-6;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

int n;
string s[60];

void solve()
{
	string res;
	for(int i=0;i<26;++i){
		char c = 'a'+i;
		bool ok = true;
		int cnt = INF;
		for(int i=0;i<n;++i){
			if(s[i].find(c) == string::npos){
				ok = false;
				break;
			}else{
				cnt = min(cnt, (int)count(s[i].begin(), s[i].end(), c));
			}
		}
		if(ok) res += string(cnt, c);
	}
	sort(res.begin(), res.end());
	cout << res << endl;
}

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

Measured memory_bytes: 256
input()
A = [int(x) for x in list(input().split())]
n = len(A)
counter = 0

for i in range(0, n-1, 1):
    minj = i
    for j in range(i, n, 1):
        if A[j] < A[minj]:
            minj = j
    if i == minj:
        continue
    tmp = A[i]
    A[i] = A[minj]
    A[minj] = tmp
    counter += 1

print(*A)
print(counter)



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

using namespace std;

const int MAX = 1e4 + 9;
int digit[11] = {2, 5, 5, 4, 5, 6, 3, 7, 6}, dp[MAX], n, m, a[MAX];

bool cmp(const int &a, const int &b) {
	return a > b;
}

void print_dp() {
	for (int i = 0; i <= n; i++) {
		cout << dp[i] << ' ';
		int n;
		cin >> n;
	}
}

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

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i]; 
		a[i]--;
	}
	dp[0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			if (i - digit[a[j]] < 0) continue;
			if (dp[i - digit[a[j]]] > 0) dp[i] = max(dp[i], dp[i - digit[a[j]]] + 1);
			//print_dp();
		}
	}
	int len = dp[n];
	string s;
	while (n) {
		vector<int> tmp;
		for (int i = 0; i < m; i++) {
			if (n - digit[a[i]] < 0) continue;
			if (dp[n - digit[a[i]]] == len - 1) {
				tmp.push_back(a[i]);
			}
		}
		sort(tmp.begin(), tmp.end(), cmp);
		s.push_back(tmp[0] + 1 + '0');
		n -= digit[tmp[0]];
		len--;
	}
	cout << s << '\n';
	
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
const int N=5e5+5, INF=1e9;
using namespace std;
int n, D, q, b[N], ans = 0, d[N], pref[N];
signed main()
{
    cin >> n >> D;
    for(int i = 1; i <= n; i++)
    {
        cin >> d[i];
    }
    pref[0]=D;
    for(int i = 1; i <= n; i++)
    {
        if(pref[i-1]>d[i]) pref[i] = pref[i-1] - d[i];
        else if(2*pref[i-1] > d[i]) pref[i] = abs(pref[i-1] - d[i]);
        else pref[i]=pref[i-1];
    }
    b[n]=1;
    for(int i = n-1; i >= 1; i--)
    {
        if(d[i+1]>=2*b[i+1])
        {
            b[i]=b[i+1];
        }
        else
        {
            b[i]=b[i+1]+d[i+1];
        }
        
    }
    /*for(int i = 1; i <= n; i++)
    {
        cout << pref[i] << " - " << b[i] << endl;
    }*/
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int x;
        cin >> x;
        if(pref[x-1] >= b[x]) cout << "YES\n";
        else cout << "NO\n";
    }
}

Measured memory_bytes: 13696
#include <iostream>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> h(N);
  rep(i, N) cin >> h[i];
  
  vector<int> c(N, 2000000000);
  c[0] = 0;
  rep(i, N) {
    rep(j, K) {
      if (i - j - 1 < 0) continue;
      c[i] = min(c[i], c[i - j - 1] + abs(h[i - j - 1] - h[i]));
    }
  }
  
  cout << c[N - 1] << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0);cin.tie(0)
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
typedef long long ll;
#define pri(n) printf("%d\n",n)
#define lpri(n) printf("%lld\n",n);
#define rep(i,st,ed) for(int i=st;i<ed;i++)
#define F first
#define S second 
#define pb(n) push_back(n)
const int N=1e5+6;
const ll M=1e9+7;
vector<int> g[N];
int visit[N],ans,dp[N];

void dfs(int node)
{
	visit[node]=1;
	for(int it:g[node])
	{
		if(!visit[it])		
			dfs(it);		
		dp[node]=max(dp[node],dp[it]+1);		
	}
	ans=max(ans,dp[node]);
}

int main()
{
	int n,m,x,y;
	scn(n);scn(m);
	set<int> st;
	for(int i=1;i<=n;i++)
		st.insert(i);
	for(int i=0;i<m;i++)
	{
		scn(x);scn(y);
		g[x].pb(y);
		st.erase(y);
	}
	for(int it:st)
	{
		dfs(it);
	}
	pri(ans);


}

Measured memory_bytes: 12800
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    rep(i, N) {
        cin >> h[i];
    }
    vector<ll> dp(N + K - 1, 10e9);
    dp[0] = 0;
    FOR(i, 0, N - 1) {
        FOR(j, 1, K + 1) {
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
        }
    }
    cout << dp[N - 1] << endl;
    return 0;
}

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

c = 0
for i in range(1,n-1):
    if (p[i-1] <= p[i] and p[i+1] >= p[i]) or (p[i-1] >= p[i] and p[i+1] <= p[i]):
        c += 1

print(c)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 64
#define LIMIT 1000000000000000000

enum Type{
	UNIQUE,
	MANY,
	NONE,
};

int N;
ull POW[NUM],input[NUM];
ull ans_A,ans_B;
Type type_array[3];

ull calc(ull num,int digit){

	if(digit == 0){

		return (num+1)/2;
	}

	ll ret = (((num+1)/POW[digit])/2)*POW[digit];

	if((num+1)%POW[digit] == 0){

		return ret;
	}

	if(((num+1)/POW[digit])%2 == 0){

		return ret;

	}else{

		return ret+(num+1)%POW[digit];
	}
}

bool is_ok(ull A,ull B,ull num,int digit){

	ull tmp = calc(B,digit)-calc(A-1,digit);

	return tmp == num;
}

bool DEBUG = false;

Type solve(ull width){

	ull A,B;

	for(int i = N-1; i >= 0; i--){

		if(input[i] > width){

			return NONE;
		}
	}

	B = 0;

	for(int i = N-1; i >= 0; i--){

		if(input[i] == width){

			B += POW[i];

		}else if(input[i] == 0){

			//Do nothing

		}else{ //input[i] < width

			B += POW[i];
			B += input[i]-1;
			break;
		}
	}

	A = B-width+1;

	if(A < 1 || B > LIMIT){

		return NONE;
	}

	for(int i = N-1; i >= 0; i--){
		if(!is_ok(A,B,input[i],i)){

			return NONE;
		}
	}

	ans_A = A,ans_B = B;

	return UNIQUE;
}

void func(){

	for(int i = 0; i < NUM; i++){

		input[i] = 0;
	}

	for(int i = 0; i < N; i++){

		scanf("%llu",&input[i]);
	}

	type_array[0] = solve(2*input[0]-1);
	type_array[1] = solve(2*input[0]);
	type_array[2] = solve(2*input[0]+1);

	int num_unique = 0;

	for(int i = 0; i < 3; i++){

		if(type_array[i] == UNIQUE){

			num_unique++;
		}
	}

	if(num_unique == 1){

		printf("%llu %llu\n",ans_A,ans_B);
	}else{

		if(num_unique >= 2){

			printf("Many\n");
		}else{

			printf("None\n");
		}
	}
}

int main(){

	POW[0] = 1;

	for(int i = 1; i < NUM; i++){

		POW[i] = POW[i-1]*2;
	}

	while(true){

		scanf("%d",&N);
		if(N == 0)break;

		func();

		if(DEBUG)break;
	}

	return 0;
}



Measured memory_bytes: 3200
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int N, W;
	cin >> N >> W;
	vector<long long int> w(N+2,0);
	vector<long long int> v(N+2,0);
	vector<vector<long long int>> dp(N+2, vector<long long int>(W+2,0));

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

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

Measured memory_bytes: 81024
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

/** ワーシャル・フロイド法による全点対最短路探索

    経路を逐次最小化していく。

    頂点番号は0オリジン。

    知らないパスにはコスト大きめを設定しておくこと。
    ただ、内部で加算するのでオーバーフローに注意。MAXダメ、絶対。
    std::fill(mat.data(), mat.data() + mat.num_elements(), MAXCOST+1);

    O(|V|^3)

    @note 反対方向もいれた？
    mat[a][b] = mat[b][a] = c;

    @note 自分自身へのルートはコスト0か？
    for (int i = 0; i < N; ++i) {
    mat[i][i] = 0;
    }

    @param[in] V  頂点数
    @param[in, out] distance[i][j]: 頂点i -> jのコスト
*/
template<typename T, typename M>
void warshall_floyd(T V, M& distance)
{
    for (T k = 0; k < V; ++k) {
        for (T i = 0; i < V; ++i) {
            for (T j = 0; j < V; ++j) {
                distance[i][j] = std::min(distance[i][j],
                                          distance[i][k] + distance[k][j]);
            }
        }
    }
}

template<typename T>
constexpr T almost_max() {
    return std::numeric_limits<T>::max() / 2 - 1;
}

int main()
{
    int64_t N, M, R;
    std::cin >> N >> M >> R;

    std::vector<int64_t> route;
    for (decltype(R) i = 0; i < R; ++i) {
        int64_t t;
        std::cin >> t;
        t--;
        route.push_back(t);
    }

    boost::multi_array<int64_t, 2> g(boost::extents[N][N]);

    std::fill(g.data(), g.data() + g.num_elements(), N * 100000);

    for (decltype(M) i = 0; i < M; ++i) {
        int64_t a, b, c;
        std::cin >> a >> b >> c;
        a--;
        b--;
        g[a][b] = g[b][a] = c;
    }

    warshall_floyd(N, g);

    int64_t ans =  INT64_MAX;

    std::sort(std::begin(route), std::end(route));

    do {
        int64_t sum = 0;
        auto route_itr = route.begin();
        int64_t prev_c = *route_itr;
        route_itr++;
        for (; route_itr != route.end(); ++route_itr) {
            sum += g[prev_c][*route_itr];
            prev_c = *route_itr;
        }
        ans = std::min(ans, sum);
    } while (std::next_permutation(route.begin(), route.end()));

    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 512
s = input()
K = int(input())

subset_list = list(s)
subset_list += [s[i:i+2] for i in range(len(s)-1)]
subset_list += [s[i:i+3] for i in range(len(s)-2)]
subset_list += [s[i:i+4] for i in range(len(s)-3)]
subset_list += [s[i:i+5] for i in range(len(s)-4)]
subset_list = list(set(subset_list))
subset_list.sort()

print(subset_list[K-1])

Measured memory_bytes: 5068
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU

signed main(){
	int n;
	cin>>n;
	vs in(n);
	rep(i,n)cin>>in[i];
	vvi a,b;
	int sum=0;
	rep(i,n){
		int co=0;
		int mi=0;
		rep(j,in[i].size()){
			if(in[i][j]=='(')co++;
			else co--;
			mi=min(mi,co);
		}
		sum+=co;
		if(co>=0)a.pb({-mi,co-mi});
		else b.pb({-co+mi,mi});
	}
	if(sum){
		cout<<"No"<<endl;
		return 0;
	}
	bool h=true;
	sort(all(a));
	sort(all(b));
	
	rep(i,a.size()){
		sum+=-a[i][0];
		if(sum<0)h=false;
		sum+=a[i][1];
	}
	rep(i,b.size()){
		sum+=b[i][1];
		if(sum<0)h=false;
		sum+=-b[i][0];
	}
	if(h)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}










Measured memory_bytes: 3256
// https://atcoder.jp/contests/abc079/tasks/abc079_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

const int INF = 1e15;

template <typename T> using Matrix = vector<vector<T>>;
template <typename T> void warshall_floyd(Matrix<T> &g, T INF) {
    REP(k, g.size()) REP(i, g.size()) REP(j, g.size()) {
        if (g[i][k] == INF || g[k][j] == INF)
            continue;
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H, W, N = 10;
    cin >> H >> W;
    Matrix<int> g(N, vector<int>(N, INF));
    REP(i, N) REP(j, N) { cin >> g[i][j]; }
    vector<vector<int>> A(H, vector<int>(W));
    REP(i, H) REP(j, W) { cin >> A[i][j]; }
    // 全点対間最短路(Warshall-Floyd)
    warshall_floyd(g, INF);
    int ans = 0;
    REP(i, H) REP(j, W) {
        if (A[i][j] >= 0) {
            ans += g[A[i][j]][1];
        }
    }
    cout << ans << endl;

    return 0;
}


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

int main(){
	int N, M, A[1010], B[1010], t[1010] = {}, a = 0;

	cin>>N>>M;
	
	for(int i = 0; i < N; i++){
		cin>>A[i];
	}	
	
	for(int i = 0; i < M; i++){
		cin>>B[i];
	}

	for(int i = 0; i < M; i++){
		for(int j = 0; j < N; j++){
			if(B[i] >= A[j]){
				t[j]++;
				break;
			}
		}
	}
	for(int i = 0; i < N; i++){
		if(t[i] >= t[a]) a = i;
	}
	
	cout<<a + 1<<endl;
	return 0;
}



Measured memory_bytes: 3108
//        ★★ ASHWINI SHARMA ★★ 
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fr(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (int i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
#define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
#define debug(x) cout<<#x<<": "<<x<<endl
#define ull unsigned long long int
#define ll long long int
#define ld double
#define ui unsigned int
#define pb push_back
#define mp make_pair
#define ff first
#define ss second 


#define PI 3.1415926535897932385
#define INF 1e18
#define EPS 1e-7
#define MAXN 1000005
#define MOD 1000000007
                                  //          ★★ ASHWINI SHARMA ★★      
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
ll exp(ll x, ll y, ll p)
{
    ll res = 1;   
    x = x % p;  
    while (y > 0)
    {
        if (y & 1)    
            res = (res*x) % p;
        y = y>>1;     
        x = (x*x) % p; 
    }
    return res;
}
ll num(ll a, ll b, ll c)
{
    ll cc = a/c;
    ll cb = b/c;
    ll x = cb-cc;
    if(a % c == 0)
        x++;
    return x;
}
ll lcm(ll a, ll b)
{
    ll y = (a*b)/gcd(a, b);
    return y;
}



int main() {
    
    fastio;
    
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll x = num(a, b, c);
    ll y = num(a, b, d);
    ll z = num(a, b, lcm(c, d));
    ll aa = x+y-z;
    aa = (b-a+1)-aa;
    cout << aa;

    return 0; 
}

Measured memory_bytes: 256
#include <cstdio>
bool d[33554432];
char k[128];

int c(char str[12]){
	int ans = str[0], i = 1;
	for(i;str[i] != '\0';i++){ans <<= 2;ans += k[str[i]];}
	return ans;
}

int main(){
	k['A'] = 0;k['C'] = 1;k['G'] = 2;k['T'] = 3;
	int n;scanf("%d", &n);
	char s[7], str[12];
	while(n--){
		scanf("%s %s", s, str);
		if(s[0] == 'i')d[c(str)] = true;
		else puts(d[c(str)] ? "yes" : "no");
	}
	return 0;
}



Measured memory_bytes: 3968
#pragma GCC optimize("O3")
#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 <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

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

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

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

    int n, k; cin>>n>>k;

    int ans = 0;
    while(n > 0){
        n /= k;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
int n, m, k;

int ar[maxn];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); //C++关同步
    int x, y;
    cin >> n >> x >> y;
    for(int i=1;i<=n;i++){
        ar[i] = n - i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int ins = min(j - i, abs(i - x) + abs(j - y) + 1);
            if(ins < j - i){
                ar[j - i]--;
                ar[ins]++;
                //cout << i << ' ' << j << ' ' << ins << '\n';
            }
        }
    }
    for(int i=1;i<n;i++)cout << ar[i] << '\n';
    return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("fma,avx")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int a;
    cin >> a;
    cout << a + a * a + a * a * a << "\n";
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n;
ll a[100010];
ll b[100010];
ll c[100010];
ll dp[100010][3];

int main()
{
	ios::sync_with_stdio(false);	
	cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i]>>c[i];
		
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
		dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
		dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
	}
	cout<<max(max(dp[n][0],dp[n][1]),dp[n][2]);
	
	return 0;
}


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

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

using namespace std;

int main(){
	int n,m; scanf("%d%d",&n,&m);
	int x[100000];
	rep(i,m) scanf("%d",x+i);

	sort(x,x+m);

	if(n>=m){ puts("0"); return 0; }

	int d[99999];
	rep(i,m) d[i]=x[i+1]-x[i];
	sort(d,d+m-1);

	printf("%d\n",accumulate(d,d+m-n,0));

	return 0;
}


Measured memory_bytes: 1024
n=[int(x) for x in input()]
for i in range(2**(len(n)-1)):
    s=n[0]
    result=[str(n[0])]
    for j in range(len(n)-1):
        if (i>>j &1)==1:
            s+=n[j+1]
            result.append("+")
        else:
            s-=n[j+1]
            result.append("-")
        result.append(str(n[j+1]))
    result.append("=7")
    if s==7:
        print("".join(result))
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

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

        int ans = 0, m = numeric_limits<int>::max();

        REP(i, n) {
                int a;
                cin >> a;

                if (a <= m) {
                        ans++;
                        m = a;
                }
        }

        cout << ans << endl;

        return 0;
}


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

using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cout << 2 * n - 1 << endl;
  if (abs(*max_element(a.begin(), a.end())) < abs(*min_element(a.begin(), a.end())))
  {
    int pos = min_element(a.begin(), a.end()) - a.begin() + 1;
    for (int i = 1; i <= n; i++)
      cout << pos << " " << i << endl;
    for (int i = n; i > 1; i--)
      cout << i << " " << i - 1 << endl;
  }
  else
  {
    int pos = max_element(a.begin(), a.end()) - a.begin() + 1;
    for (int i = 1; i <= n; i++)
      cout << pos << " " << i << endl;
    for (int i = 1; i < n; i++)
      cout << i << " " << i+1 << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

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

	scanf("%d", &n);

	for (i = 1; i <= n; i++) {
		if (i % 3 == 0) printf(" %d", i);
		else {
			c = i;

			while (c % 10 != 3 && c > 0) {
				c /= 10;
				}
			
			if (c > 0) printf(" %d", i);
		}
	}

	printf("\n");

	return 0;
}

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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<ll> acc(N + 1);
    for (int i = 0; i < N; i++) {
        acc[i + 1] = acc[i] + A[i];
    }

    map<ll, ll> cnt;
    ll ans = 0;
    for (int i = 0; i < N + 1; i++) {
        ans += cnt[acc[i]];
        cnt[acc[i]]++;
    }
    cout << ans << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

Measured memory_bytes: 15104
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define ll long long
#define N 1010
using namespace std;
int n,a[N],top,ans[N]; 
ll f[N],p[N];
int read()
{
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		f[i]=a[i],p[i]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if((i-j)%2==0)
				if(f[j]+a[i]>f[i]) p[i]=j,f[i]=f[j]+a[i];
	f[0]=-1e9;
	int id=0;			
 	for(int i=1;i<=n;i++)
    	if(f[i]>f[id]) id=i;
    printf("%lld\n",f[id]);
    top=0;
	for(int i=n;i>id;i--)
		ans[++top]=i;
	int pos=id;
	for(;p[pos]>0;pos=p[pos])
		for(int i=(pos+p[pos])/2;i>p[pos];i--)
			ans[++top]=i;
	for(int i=pos-1;i;i--)
		ans[++top]=1;
	printf("%d\n",top);
	for(int i=1;i<=top;i++)
		printf("%d\n",ans[i]);			
	return 0;
}



Measured memory_bytes: 256
N,Y = map(int, input().split())
a = Y//10000
b = (Y%10000)//5000
c = (Y%5000)//1000
for i in range(a+1):
    x = a-i
    y = b + i * 2
    for j in range(y+1):
        z = c + j * 5
        if x+y-j+z == N:
            print("{} {} {}".format(x,y-j,z))
            exit()
        if x+y-j+z > N:
            break
print("-1 -1 -1") 

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

#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define all(v) v.begin(), v.end()
#define ar array

#define F first
#define S second
#define sz(x) int(x.size())
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
using ld = long double;

const int mod = 1e9 + 7;
// const int mod = 998244353;
const ll inf = 2e9;
const ll INF = 2e18;
const ld EPS = 1e-7;

const int N = 2e5 + 5;

int go[N];

bool u[N];

int d[N];

bool ok = 0;

ll k;

void dfs (int v) {
	// cout << v + 1 << " ";
	if (!k) {
		cout << v + 1;
		exit(0);
	}
	u[v] = 1;
	int to = go[v];
	if (u[to] && !ok) {
		ll dist = d[v] - d[to] + 1;
		k %= dist;
		if (!k) {
			cout << v + 1;
			exit(0);
		}
		ok = 1;
		--k;
		dfs (to);
	}
	else {
		--k;
		d[to] = d[v] + 1;
		dfs (to);
	}
}

void solve () {
	int n;
	cin >> n >> k;
	for (int i = 0 ; i < n ; ++ i) {
		cin >> go[i];
		go[i]--;
	}
	dfs (0);
}

int main () {
	ios;
	int tt = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		cout << "\n";
	}
}

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

int main(){
  int N; cin >> N;
  vector<int> x(N), y(N);
  rep(i,N) cin >> x[i] >> y[i];
    
  int cnt = 0;
  double sum = 0;
  rep(i, N) rep(j, N) {
    if (i == j) continue;
    cnt++;
    sum += sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
  }

  double ans = (N - 1) * sum / cnt;
  printf("%.12f\n", ans);
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
int a[1000],i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=n-1;i>=1;i--)
{
printf("%d ",a[i]);
}
printf("%d\n",a[0]);
return 0;
}


Measured memory_bytes: 2724
#include <iostream>
#include <climits>
#include <bitset>
#include <stack>
#include <queue>
#include <iomanip>
#include <limits>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
 
using namespace std;
typedef long long ll;
 
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define re(i,a,b) for(i=a;i<=b;i++)
 
ll i,j,k,ii,jj;
ll n,m,sum,num=INF;
ll ans;
ll a,b,c,d,e;
ll x[100005],y[100005],z[100005];
ll xa[100005],ya[100005],za[100005];
ll dp[100005];
string s;

int main(){
	cin>>n>>m;
    for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cin>>s;
			if(s=="snuke"){
				char sa[10];
				sa[10]=j+'A';
				cout<<sa[10]<<i+1<<endl;
				return 0;
			}
		}
	}

}

Measured memory_bytes: 6272
import math
from collections import defaultdict,deque
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:list(input())
ips=lambda:input().split()

"""========main code==============="""

def fast_expo(x,y,m):
    res=1
    while(y):
        if(y&1):
            res*=x
            res%=m
        x*=x
        x%=m
        y>>=1
    return res    

dp=defaultdict(int)
dp[1]=1
dp[2]=1
for i in range(3,200001):
    k=i
    cnt=0
    while(k):
        if(k%2): cnt+=1
        k>>=1
    dp[i]=dp[i%cnt]+1
n=ii()
a=ip()
a=a[::-1]
c=a.count('1')

min_1=0
max_1=0

for i in range(n):
    if(a[i]=='1'):
        if(c-1!=0):
            min_1+=fast_expo(2,i,c-1)
            min_1%=(c-1)
        max_1+=fast_expo(2,i,c+1)
        
        max_1%=(c+1)
    
ans=[]    

for i in range(n):
    if(a[i]=='1'):
        if(c-1==0):
            ans.append(0)
        else:    
            ans.append(dp[(min_1-fast_expo(2,i,c-1)+(c-1))%(c-1)]+1)
    else:
        ans.append(dp[(max_1+fast_expo(2,i,c+1))%(c+1)]+1)
ans=ans[::-1]
for i in ans:
    print(i)

Measured memory_bytes: 114500
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <vector>

using namespace std;


int main() {
    int H, W; 
    int C[10][10];
    int Cost[10][10];
    std::vector<std::vector<int>> wall;

    scanf("%d %d", &H, &W);
    for (int i = 0; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
	    int data; scanf("%d", &data);
	    C[i][j] = data;
	    Cost[i][j] = data;
	}
    }

    wall.resize(H);
    for (int i = 0; i < H; i++) {
	wall[i].resize(W);
    }
    for (int i = 0; i < wall.size(); i++) {
	for (int j = 0; j < wall[i].size(); j++) {
	    int data; scanf("%d", &data);
	    wall[i][j] = data;
	}
    }

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

    int sumCost = 0;
    for (int i = 0; i < wall.size(); i++) {
	for (int j = 0; j < wall[i].size(); j++) {
	    if (wall[i][j] == -1 || wall[i][j] == 1) {
		continue;
	    }
	    else {
		sumCost += Cost[wall[i][j]][1];
	    }
	}
    }
    printf("%d\n", sumCost);
}



Measured memory_bytes: 384
using System;
using System.Linq;

namespace abc123
{
    class A
    {
        static void Main(string[] args)
        {
            int a = Input.Int();
            int b = Input.Int();
            int c = Input.Int();
            int d = Input.Int();
            int e = Input.Int();
            int k = Input.Int();

            if (e - a <= k)
            {
                Console.WriteLine("Yay!");
            }
            else
            {
                Console.WriteLine(":(");
            }

        }
    }

    internal static class Input
    {
        public static int Int() => int.Parse(Console.ReadLine());

        public static string Str() => Console.ReadLine();

        public static int[] IntArray() => Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

    }

}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;


int main(){
    string s;
    cin >> s;
    bool ok = true;
    for(int i = 0; i < s.size(); i++){
        if(i % 2 == 0 && s[i] != 'h'){
            ok = false;
        }
        if(i % 2 == 1 && s[i] != 'i'){
            ok = false;
        }
    }
    if(ok && s.size() % 2 == 0){
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256