akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e15)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define arrdump(n,a) for(int i=0;i<n;i++) {cout<<((i>0)? " ":"")<<a[i];}cout<<"\n";


typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://atcoder.jp/contests/abc101/tasks/arc099_a

int main() {
    int N, K; cin >> N >> K;

    int cnt = 0;
    while (N > 0) {
        if (cnt == 0) N-=K;
        else N-=(K-1);
        cnt++;
    }
    cout << cnt << "\n";

    return 0;
}

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

int main() {
	int a;
	while (scanf("%d", &a), a) {
		int coin[] = { 500,100,50,10,5,1 };
		a = 1000 - a;
		int cnt = 0;
		rep(i, 6) {
			while (a - coin[i] >= 0) {
				a -= coin[i];
				cnt++;
			}
			if (a == 0)break;
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Measured memory_bytes: 1188
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{	
public static void main (String[] args){
	Scanner sc = new Scanner(System.in);
	int n = Integer.parseInt(sc.next());
	int l = Integer.parseInt(sc.next());
	int sum = n*(n+2*l-1)/2;
	int min = l;
	
	for(int i = 0; i < n;i++){
		if(Math.abs(l+i-1) > Math.abs(l+i)) min = l+i;
	}
	System.out.println(sum-min);
}
}


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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}





void _main() {
        int n; cin >> n;
        vector<int> a(n); cin >> a;
        sort(all(a));
        cout << abs(a.back() - a.front());
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, H, W, A, B;
    cin >> N >> H >> W;

    int ans = 0;
    REP(i, N) {
        cin >> A >> B;
        if (H <= A && W <= B) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define rn(i,n) for(int i=1;i<=n;i++)
#define ll long long


int main(){
  int n;
  cin>>n;
  vector<vector<int> > h(n, vector<int>(100,0));
  vector<int> a(n);
  int sum=0;
  r(i,n){
    int tmp;
    cin>>tmp;
    a.at(i)=tmp;
    r(j,tmp){
      h.at(i).at(j)=1;
    }
    sum+=tmp;
  }

  for(int i=1;i<n;i++){
    r(j,a.at(i)){
      if(h.at(i).at(j)==1&&h.at(i-1).at(j)==1)sum--;
    }
  }
cout<<sum<<endl;


  return 0;

}


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

int main(){
  int n,i,r,j,nu,k;
  cin >> n;
  vector<string> s(n);
  map<char,int> mp;
  vector<int> ans(26,100);
  for(i=0;i<n;++i){
    cin >> s[i];
    int a[30] ={0};
    for(j=0;j<s[i].size();++j){
      int x=s[i][j]-'a';
      a[x]++;
    }
    for(j=0;j<26;++j){
      ans[j]=min(ans[j],a[j]);
    }
  }
  string anss;
  for(i=0;i<26;++i){
    char z=i+97;
    if(ans[i]>0 && ans[i]!=100){
      r=0;
      while(r<ans[i]){
        anss=anss+z;
        r++;
      }
    }
  }
  cout << anss << endl;
  return 0;



}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int N,n;
  int sum = 0;
  cin >> N;
  n = N;
  while(n>10){                                                                          sum += n%10;
    n = n/10;
  }
  sum += n;
  if(N%sum == 0) cout << "Yes" << "\n";
  else  cout << "No" << "\n";
  return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    multiset<int> D;
    REP(i, 0, N) {
        int d; cin >> d;
        D.insert(d);
    };

    int M; cin >> M;
    bool ok = true;
    REP(i, 0, M) {
        int t; cin >> t;
        auto itr = D.find(t);
        if (itr != D.end()) {
            D.erase(itr);
        } else {
            ok = false;
        }
    }

    if (ok) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

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

typedef long long int ll;
#define PI 3.14159265

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll k;
  cin>>k;
  string s;
  cin>>s;
  ll n=s.length();
  if(n<=k){
    cout<<s;
  }
  else{
    ll i;
    string ans;
    for(i=0;i<k;i++){
      ans+=s[i];
    }
    ans+="...";
    cout<<ans<<endl;
  }
  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
ll gcd(ll a, ll b){
  if(b==0) return a;
  else gcd(b,a%b);
}
ll lcm(ll a, ll b){
  return a/gcd(a,b)*b;
}
int main(){
  string s,t,u;
  int a,b;
  cin >> s >> t >> a >> b >> u;
  if(s==u) cout << a-1 << " "  << b << endl;
  else cout << a << " " << b-1 << endl;
  
  return 0;
}


Measured memory_bytes: 256
/*
ÂmÂ[ÂhÂÃ° n/2 ÂÃÂÃ2ÂÃÂÃÂOÂÂÂ[ÂvÂÃÂÂªÂÂ¯ÂÃ©

  ÂOÂÂÂ[Âv1   ÂOÂÂÂ[Âv2
  ---------   ---------
          1           0
          2           5
          3           4

ÂÂ±ÂÃ2ÂÃÂÃÂOÂÂÂ[ÂvÂÃ°ÂÃÂÂºÂÃÂÂÂÃÂÃÂMÂUÂMÂUÂÃÂÃÂÃÂÂ°ÂÃ©ÂÃ1ÂpÂ^Â[ÂÂÂÃÂÂ«ÂÂ ÂÂªÂÃ©.
  0 -> 1 -> 5 -> 2 -> 4 -> 3

ÂÂ³ÂÃ§ÂÃ, ÂÂ±ÂÃÂpÂ^Â[ÂÂÂÃ°ÂÂ½ÂÂÂvÂÃ±ÂÃ¨ÂÃÂÂÂÃÂÃÂÃ±Â]ÂÂ³ÂÂ¹ÂÃÂÂ¢ÂÂ­ÂÃ,
  0 -> 1 -> 5 -> 2 -> 4 -> 3
  1 -> 2 -> 0 -> 3 -> 5 -> 4
  2 -> 3 -> 1 -> 4 -> 0 -> 5
ÂÃÂÃ°ÂÂ¤ÂLÂÂµÂÃÂÂ¢(n / 2)ÂÃÂÃÂSÂÃ¦ÂÃÂÃ°ÂÂ¾ÂÃ©ÂÂ±ÂÃÂÂªÂÃÂÂ«ÂÃ©.

n=ÂÃ´ÂÂÂÃÂÂ ÂÃ©ÂÃÂÂ«, ÂÂ±ÂÃÂ@ÂÂ¥ÂÃÂÂµÂÂ½ÂÂªÂÃÂÃÂSÂÃ¦ÂÃÂÃ°ÂgÂÃÂÃÂÂ¢ÂÃÂÂ½ÂÃªÂÂ,
ÂSÂÃ¦ÂÃÂÃÂgÂÃ­ÂÃÂÂ¢ÂÃ¦ÂÂ¤ÂÃÂÂ³ÂÃÂÃÂGÂbÂWÂÂª1ÂÃÂÃ ÂÂ­ÂÂ¶ÂÂµÂÃÂÂ¢.

ÂÂ±ÂÃÂÂ±ÂÃÂÂ©ÂÃ§, ÂÂ±ÂÃÂÃ»Â@ÂÂªÂÃªÂÃÂÂ½ÂÂ­ÂÂ³ÂÃ±ÂSÂÃ¦ÂÃÂÃ°ÂÃ¬ÂÃ©ÂÂ±ÂÃÂÂªÂÃÂÂ«ÂÃ©.


ÂÂÂÂ½ÂÃÂÂ
  ÂoÂÃÂÂªÂÂ½ÂÂ·ÂÂ¬ÂÃ©ÂÃÂ\ÂzÂÃÂÂ«ÂÃ©ÂÃªÂÂÂÃ, printfÂÃ°ÂgÂÂ¤

 */

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int n, k;

  while(cin >> n >> k){
    if(n / 2 < k){
      printf("-1\n");
      //cout << "-1\n";
      continue;
    }

    int p[n + 2];
    p[0] = 0;

    for(int i = 1; i < n; i += 2){
      p[i] = i / 2 + 1;
      p[i + 1] = n - p[i];
    }

    for(int i = 0; i < k; i++){
      if(i != 0) printf("\n");

      for(int j = 0; j < n - 1; j++){
        int a = (p[j] + i) % n + 1;
        int b = (p[j + 1] + i) % n + 1;
        printf("%d %d\n", a, b);
        //cout << a << " " << b << endl;
      }
    }
  }
}

Measured memory_bytes: 912
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

const int NN = 6, CC = 51;
double dp[2][NN*CC+1][1<<NN][1<<NN];

int main() {
	int n, len;
	cin >> n >> len;
	vector<int> in(n);
	for(int & x : in) cin >> x;
	sort(in.rbegin(), in.rend());
	dp[0][n*in[0]][1][1] = 1;
	for(int start = 0; start < n * len; ++start) {
		int old = start % 2;
		int nowy = old^1;
		for(int end = 0; end <= n * len; ++end)
			for(int mask_used = 0; mask_used < (1 << n); ++mask_used)
				for(int mask_places = 0; mask_places < (1 << n); ++mask_places)
					dp[nowy][end][mask_used][mask_places] = 0;
		for(int end = start; end <= n * len; ++end)
			for(int mask_used = 0; mask_used < (1 << n); ++mask_used)
				for(int mask_places = 0; mask_places < (1 << n); ++mask_places) {
					double me = dp[old][end][mask_used][mask_places];
					if(me <= 1e-15) continue;
					debug() << imie(start) imie(end) imie(mask_used) imie(mask_places) imie(me);
					dp[nowy][end][mask_used][mask_places] += me;
					int bit = start % n;
					if(mask_places & (1 << bit)) continue;
					for(int who = 0; who < n; ++who)
						if(!(mask_used & (1 << who))) {
							debug() << "-> " << start+1 << " " << min(n*len, max(end, start + n * in[who]))
								<< " " << (mask_used|(1<<who)) << " " << (mask_places|(1<<bit));
							dp[nowy][min(n*len, max(end, start + n * in[who]))]
									[mask_used|(1<<who)][mask_places|(1<<bit)] += me / len / __builtin_popcount(mask_used);
						}
				}
	}
	double answer = dp[(n*len)%2][n*len][(1<<n)-1][(1<<n)-1];
	printf("%.13lf\n", answer);
}


Measured memory_bytes: 19840
#include <algorithm>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Pause system("pause")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 10;
int a[maxn];
bool cmp(int x, int y)
{
    return x > y;
}
int main()
{
    IOS;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        if (i + 1 > a[i + 1])
        {
            int j = 0;
            for (; a[i + j + 1] == i; j++)
                ;
            if ((a[i] - i) % 2 == 1 || j % 2 == 1)
                cout << "First"<<endl;
            else
                cout << "Second"<<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3512
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main(){
  int n, k, tmp, ans=1000000000, i, j;
  cin >> n >> k;
  int h[n];
  for(i=0; i<n; i++)
    cin >> h[i];
  sort(h, h+n);
  for(j=0; j<=n-k; j++){
    tmp=h[j+k-1]-h[j];
    if(tmp<ans) ans=tmp;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

ll mypow(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll tmp = mypow(a, b / 2);
    if (b % 2)
        return (((tmp * tmp) % MOD) * a) % MOD;
    else
        return (tmp * tmp) % MOD;
}

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

    string z, o;
    cin >> z >> o;
    int n;
    cin >> n;
    int zsz = z.size(), osz = o.size();
    if (n <= osz)
    {
        string orev = o;
        reverse(orev.begin(), orev.end());
        string hoge = orev.substr(0, n);
        string s = hoge + z + hoge + o, srev = s;
        reverse(srev.begin(), srev.end());
        cout << (s == srev ? 1 : 0) << endl;
        return 0;
    }
    string s = o;
    reverse(s.begin(),s.end());
    string t = z + s, trev = t;
    reverse(trev.begin(),trev.end());
    if(t != trev)
    {
        cout << 0 << endl;
        return 0;
    }
    int len = n - osz;
    cout << mypow(26, (len+1)/2) << endl;
}



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

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

using namespace std;
using lint=long long;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint pow(mint m,long long k){
	mint res=1;
	for(;k>0;k>>=1,m*=m) if(k&1) res*=m;
	return res;
}

template<class T> T gcd(const T& a,const T& b){ return b==0?a:gcd(b,a%b); }

mint f(lint H,lint W,lint T){
	if(T==1) return pow(mint(2),H)+pow(mint(2),W)+pow(mint(2),gcd(H,W))-3;
	else     return pow(f(H/gcd(H,T),W/gcd(W,T),1),gcd(H,T)*gcd(W,T));
}

int main(){
	lint H,W,T; cin>>H>>W>>T;
	cout<<f(H,W,T)<<'\n';
	return 0;
}


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

int main() {
	int h, w; cin >> h >> w;
	char a[105][105];
	char b[105][105];

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			cin >> a[y][x];
		}
	}

	for (int y = 0; y < h + 2; y++) {
		for (int x = 0; x < w + 2; x++) {
			b[y][x] = '#';
		}
	}

	for (int y = 0; y < h; y++) {
		for (int x = 0; x < w; x++) {
			b[y+1][x+1] = a[y][x];
		}
	}

	for (int y = 0; y < h+2; y++) {
		for (int x = 0; x < w+2; x++) {
			cout << b[y][x];
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 256
# 幅優先探索（行きがけ）
import collections
import sys
import copy


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()

    num = 0

    for i in range(1, N+1):
        y = N//i
        num += int((y*(y+1)*i)/2)

    print(num)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9608
N, K = map(int, input().split())

# x個の選んだ際の合計値の最小 から 最大 の間の数すべてがx個選んだ際の合計値になりうると仮定

def one_to_a_sum(a):
    return (a+1)*a//2

def a_to_b_sum(a, b):
    return one_to_a_sum(b) - one_to_a_sum(a-1)

sum_num = 0
for i in range(K, N+2):
    min_num = a_to_b_sum(0, i-1)
    max_num = a_to_b_sum(N-(i-1), N)
    sum_num = (sum_num + max_num-min_num+1) % (10**9+7)

print(sum_num)


Measured memory_bytes: 9124
import sys
input = sys.stdin.readline

def main():
    A, B = map(int, input().split())
    s = input().strip()

    ok = True
    for i in range(A + B):
        if i == A:
            if s[i] != "-":
                ok = False
                break
        else:
            if s[i] not in "0123456789":
                ok = False
                break
    
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

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

int main()
{
   long long n, a, b;
	cin >> n >> a >> b;
	if(a > b) 
    {
      long long t=a;
      a=b;
      b=t;
    }
	long long diff = b - a;
	if(diff % 2 == 1){
		long long left = a;
		long long right = n - b + 1;
		cout << min(left, right) + diff / 2 << endl;
	}else{
		cout << diff / 2 << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int key[1000];
string s,ans[1000];
int main(void){
	while(1){
		int d;
		cin >>d;
		if(d==0)break;
		for(int i=0;i<d;i++){
			cin >>key[i];
		}
		cin >>s;
		for(int i=0;i<s.length();i++){
			int keynum=i%d;
			for(int j=0;j<key[keynum];j++){
				if(s[i]=='a'){
					s[i]='Z';
				}else if(s[i]=='A'){
					s[i]='z';
				}else{
					s[i]-=1;
				}
			}
		}
		cout << s <<endl;
	}
}

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

int main(){
  ll N,M;
  cin >>N>>M;
  int count=0;
  vector<int> H(N);
  vector<int> A(M);
  vector<int> B(M);
  vector<bool> ans(N,true);
  
  //展望台高さ登録
  for(int i=0;i<N;i++){
    cin >> H.at(i);
  }
  
  //橋登録
  for(int i=0;i<M;i++){
    cin >> A.at(i) >> B.at(i);
    A.at(i)--;B.at(i)--;
  }
  //橋の相手が高いければfalse
  for(int i=0;i<M;i++){
    if(H.at(A.at(i))>=H.at(B.at(i))){ans.at(B.at(i))=false;}
    if(H.at(B.at(i))>=H.at(A.at(i))){ans.at(A.at(i))=false;}
  }
  
  for(int i=0;i<N;i++){
    if(ans.at(i))count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 4556
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int A, B;
    cin >> A >> B;
    if (A > B)
        swap(A, B);

    if (A % 2 != B % 2)
        cout << "IMPOSSIBLE";
    else
        cout << (A + B) / 2;
    cout << endl;
    return 0;
};


Measured memory_bytes: 256
package main

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

var (
	readString func() string
	readBytes  func() []byte
	stdout     *bufio.Writer
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), math.MaxInt32)
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		return []byte(f1())
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func max64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func abs64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func gcd64(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd64(b, a%b)
}

// readString() string
// readInt() int
// readInt64() int64
// readFloat64() float64

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	a := readInt()
	b := readInt()
	c := readInt()
	ans := min(min(a+b, b+c), c+a)
	println(ans)
}

// -----------------------------------------------------------------------------


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

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

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  ll A,B,K;
  cin >> A >> B >> K;

  for(int i = 0; i < K; i++){
    if(i%2==0){
      ll tmpa;
      if(A%2==0){
        tmpa = A / 2;
        A -= tmpa;
      } else { 
        A -= 1;
        tmpa = A / 2;
        A -= tmpa;
      }
      B += tmpa;
    } else { 
      ll tmpb;
      if(B%2==0){
        tmpb = B / 2;
        B -= tmpb;
      } else { 
        B -= 1;
        tmpb = B / 2;
        B -= tmpb;
      }
      A += tmpb;
    }
  }

  cout << A << " " << B << endl;
}



Measured memory_bytes: 3596
/**
 * ?¨??????????

n ????????????????????????????????§????????°???????????°???????¨?????????£??????????????????????????????s1, s2 ... sn??¨????????¨??????????¨??????????????±???????????????°????????????????????????

??????????????????????????¨????????°????????£?±2?????\???????????§???????????????

?±2 = (???ni=1(si - m)2)/n

?????£?????£????????????????¨???????????±??¨?????????

Input
?????°??????????????????????????\?????¨??????????????????????????????????????????????????\????????¢?????§??????????????????

???????????° n
s1 s2 ... sn
n ??? 0 ?????¨?????\?????????????????¨?????????

Output
?????????????????????????????????????¨?????????????????????????????????????????????????0.0001??\????????????????????£???????????????

Constraints
??\?????§??????????????? n ???1000????¶????????????¨????????????
0 ??? si ??? 100
Sample Input
5
70 80 100 90 20
3
80 80 80
0
Sample Output
27.85677655
0.00000000
 */

#include <iostream>
#include <sstream>
#include <cmath>
#include <valarray>
#include <iomanip>

int main(int argc, char const *argv[]) {
  unsigned short n;
  unsigned int s;
  std::string Param;
  std::istringstream iss;

  while (true) {
    getline(std::cin, Param);
    iss.str(Param);
    iss >> n;
    iss.clear();
    if (n != 0) {
      std::valarray<double> si((double)0, n);
      getline(std::cin, Param);
      iss.str(Param);

      for (size_t i = 0; i < n; i++) {
        iss >> s;
        si[i] = s;
      }
      iss.clear();
      double m = si.sum() / n;
      double a = sqrt(pow(si - m, 2).sum() / n);
      std::cout << std::fixed << std::setprecision(8) << a << std::endl;
    } else {
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 3228
#include <stdio.h>
#include <math.h>
int main () {
	int d, i;
	int area = 0;
	while (scanf ("%d", &d) != EOF) { 
		area = 0;
		for (i = 0;i < 600;i += d) {
			area += d * pow (i,2);	
		}
		printf ("%d\n", area);
	}
	return 0;
}

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

using namespace std;

#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
//s = char []
#define ss(s) scanf("%s",&s)
//s = string to read with spaces
#define read(s) getline(cin,s)

int main()
{
    int h,w,n;
    si(h);si(w);si(n);
    vector<int> arr(n+1);
    int mat[h][w];
    for(int i=1;i<=n;i++)si(arr[i]);
    bool direction = 1;
    int row = 0 , ind = 1;
    int startt = 0,endd = w-1;
    while(ind<=n){
        if(direction){
            int j;
            for(j =startt;j<=endd && arr[ind] >= 1;j++){
                arr[ind]--;
                mat[row][j] = ind;
            }
            if(arr[ind] >= 1){
                direction = direction^1;
                startt = 0;
                endd = w-1;
                row++;
            }
            else{
                ind++;
                if(j > endd){
                    startt = 0;
                    endd = w-1;
                    row++;
                }
                else{
                    startt = j;
                    endd = w-1;
                }
            }
        }
        else{
            int jj;
            for(jj = endd;jj>=startt && arr[ind] >= 1;jj--){
                arr[ind]--;
                mat[row][jj] = ind;
            }
            if(arr[ind] >= 1){
                direction = direction^1;
                startt = 0;
                endd = w-1;
                row++;
            }
            else{
                ind++;
                if(jj < startt){
                    startt = 0;
                    endd = w-1;
                    row++;
                }
                else{
                    startt = 0;
                    endd = jj;
                }
            }
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout << mat[i][j];
            if(j!=w-1)cout << " ";
        }
        if(i!=h-1)cout << "\n";
    }
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<stack>/*** LIFO *** stack<type> var;
push(), top():to get data, pop():to remove, size(), empty() ***/
using namespace std;

#define Fp(I, STAT, END) for(int I = STAT; I < END; I++)
#define Fm(I, STAT, END) for(int I = STAT; I > END; I--)

int main(){
    int A, B;
    cin >> A >> B;
    if(A + B < A - B){
        if(A - B < A * B) cout << A * B << endl;
        else cout << A - B << endl;
    }else{
        if(A + B < A * B) cout << A * B << endl;
        else cout << A + B << endl;
    }
}

Measured memory_bytes: 256
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    n=int(input())
    a=[int(x) for x in input().split()]
    d={}
    for i,x in enumerate(a):
        # print(i,x)
        if i-x in d:
            d[i-x]+=1
        else:
            d[i-x]=1
    ans=0

    for i,x in enumerate(a):
        d[i-x]-=1
        # print(i,x)
        if i+x in d:
            ans+=d[i+x]
    
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Measured memory_bytes: 110748
import collections


def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    q = int(input())
    ans = sum(targets)

    targets = collections.Counter(targets)

    for i in range(q):

        b, c = map(int, input().split())
        num_of_b = targets[b]
        targets.update({c: num_of_b})
        del targets[b]
        ans += (c-b)*num_of_b
        print(ans)

resolve()

Measured memory_bytes: 91916
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#include "atcoder/all"

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;
const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    friend std::istream &operator>>(std::istream &in, mint &o) {
        ll a;
        in >> a;
        o = a;
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const mint &o) {
        out << o.x;
        return out;
    }

};

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

    vector<P> v(k);
    for (P &p : v) cin >> p.first >> p.second;

    vector<mint> dp(n * 3, 0);
    dp[0] = 1;

    rep(i, n) {
        if (i == 0) continue;
        dp[i] += dp[i - 1];
        mint from = dp[i];
        for (P p : v) {
            dp[i + p.first] += from;
            dp[i + p.second + 1] -= from;
        }

    }

//    rep(i, n) {
//        if (i == 0) continue;
//        dp[i] += dp[i - 1];
//    }
    cout << dp[n] << endl;

}


Measured memory_bytes: 7956
#include <bits/stdc++.h>
using namespace std;
 
int main() {

  string S;

  cin >> S ;

  bool a=true,b=true,c=true;

  int N = S.size();

  for(int i=0;i<N/2;i++){
    if(S.at(i)!=S.at(N-1-i)) a=false;
  }//回文か

  for(int i=0;i<(N-1)/4;i++){
    if(S.at(i)!=S.at((N-1)/2-i-1)) a=false;
  }//前半部回文か

  for(int i=0;i<(N-1)/4;i++){
    if(S.at((N+3)/2+i-1)!=S.at(N-1-i)) a=false;
  }//後半部回文か


  if(a&&b&&c) cout << "Yes" << endl;

  else cout << "No" << endl;
 
  return 0;
}

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

int main()
{
    //freopen("input.txt", "r", stdin);


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

    int* a = new int[n];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", a + i);
        a[i] -= i + 1;
    }

    sort(a, a + n);
    int b = a[n / 2];

    long long ans = 0;
    for (int i = 0; i < n; ++i)
        ans += 1LL * abs(a[i] - b);

    printf("%lld", ans);

}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
// template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE


typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define Mod 1000000007
#define MAX 5002

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll a,b;cin>>a>>b;

	ll g = __gcd(a,b);

	if(g==1){
		cout<<1<<endl;
		return 0;
	}

	vector<ll> primes;
	for(ll i=2;i*i<=g;i++)
	{
		if((g%i)==0){
			primes.pb(i);
			while(g%i==0){
				g = g/i;
			}
		}
	}
	if(g>1) primes.pb(g);
	cout<<primes.size()+1<<endl;






























	
}

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

int n, k, ans;

int main() {
  cin >> n >> k;
  vector<int> h(n);
  ans = 1000000000;
  rep(i, n) cin >> h[i];
  sort(h.rbegin(), h.rend());
  rep (i, n-k+1) {
    ans = min(ans, h[i] - h[i+k-1]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3736
S = input()
T = input()

s_len = len(S)
t_len = len(T)

answer = 0
for i in range(s_len - t_len + 1):
  count = 0
  for j in range(t_len):
    if S[i+j] == T[j]:
      count += 1
  answer = max(answer, count)

print(str(t_len - answer))

Measured memory_bytes: 9116
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct pnt {
	int x, y;
	constexpr pnt(int x = 0, int y = 0) noexcept : x(x), y(y) {};
	constexpr bool operator==(const pnt &rhs) const noexcept { return x == rhs.x && y == rhs.y; }
	constexpr bool operator<(const pnt & rhs) const noexcept { return x < rhs.x || x == rhs.x && y < rhs.y; }
	constexpr pnt operator+(const pnt &rhs) const noexcept { return pnt(x + rhs.x, y + rhs.y); }
	constexpr pnt operator-(const pnt &rhs) const noexcept { return pnt(x - rhs.x, y - rhs.y); }
	constexpr pnt operator-() const noexcept { return pnt(-x, -y); }
	constexpr int operator*(const pnt &rhs) const noexcept { return x * rhs.x + y * rhs.y; }
	friend istream& operator>>(istream& is, pnt &p) { return is >> p.x >> p.y; }
	friend ostream& operator<<(ostream& os, const pnt &p) { return os << p.x << " " << p.y << "\n"; }
	constexpr pnt nor(const pnt &rhs) const noexcept { return pnt(rhs.y, -rhs.x); }
	template<class T> T& operator[](vector<vector<T>> &v) { return v[x][y]; }
};

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

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int H, W;
	cin >> H >> W;

	vector<vector<char>> grid(H, vector<char>(W));
	for (int i = 0; i < H; i++) for (int j = 0; j < W; j++)  cin >> grid[i][j];
	DMP(grid);

	auto shortest_path = [&](pnt st, pnt go) {

		if (st[grid] == '#' || go[grid] == '#') return 0;
		
		queue<pnt> que;
		que.emplace(st);
		vector<vector<int>> used(H, vector<int>(W, INF));
		st[used] = 0;

		while (!que.empty()) {

			pnt now = que.front();
			que.pop();
			if (now == go) continue;

			vector<pnt> dxdy{ {-1,0},{1,0},{0,1},{0,-1} };
			for (const auto &d : dxdy) {
				pnt next = now + d;
				if (0 <= next.x && next.x < H && 0 <= next.y && next.y < W && next[grid] == '.' && next[used] == INF) {
					que.emplace(next);
					next[used] = now[used] + 1;
				}
			}

		}
		DMP(used);
		return go[used];

	};

	int ans = 0;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			for (int k = i; k < H; k++) {
				for (int l = 0; l < W; l++) {
					chmax(ans, shortest_path(pnt(i, j), pnt(k, l)));
				}
			}
		}
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)

def main():
    MOD = 10 ** 9 + 7
    l = [int(char) for char in input()]

    n = len(l)

    cumsum = []
    tmp = 0
    for number in l:
        if number == 1:
            tmp += 1
        cumsum.append(tmp)
    sel = [pow(2, number, MOD) for number in cumsum]
    sel.append(1)

    def dp(i, _cache={-1: 0}):
        if i in _cache:
            return _cache[i]
        if l[i] == 0:
            result = dp(i-1)
            _cache[i] = result
            return result
        result = dp(i-1) + sel[i-1] * pow(3, n - 1 - i, MOD)
        result %= MOD
        _cache[i] = result
        return result
    
    answer = dp(n-1) + sel[n-1]
    answer %= MOD
    print(answer)


main()


Measured memory_bytes: 121080
#include<cstdio>
#include<bitset>
using namespace std;
int n,a[2005],w[4000005],cnt;
bitset<4000005>c;
int main()
{
	scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]);c[0]=1;
	for(int i=1;i<=n;++i) c|=c<<a[i];
	for(int i=0;i<=4000000;++i) if(c[i]) w[++cnt]=i;
	printf("%d",w[cnt/2+1]);
	return 0;
}

Measured memory_bytes: 11392
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
#define ins insert
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5, inf = 1e9;
map < int , set < int > > g[N];
bool used[N];
int d[N];
deque < int > layer;
set < pair < int , int > > was;
void dfs(int &st , int v , int C){
    if(d[v] > d[st] + 1){
        d[v] = d[st] + 1;
        layer.pb(v);
    }
    was.insert({v , C});
    for(auto u : g[v][C])
        if(was.find({u , C}) == was.end())
        dfs(st , u , C);
}
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n , m; cin >> n >> m;
    for(int i = 0 ; i < m; ++i){
        int p , q , c;cin >> p >> q >> c;
        --p, --q;
        g[p][c].ins(q);
        g[q][c].ins(p);
    }


    fill(d , d + N , inf);
    d[0] = 0;
    layer.pb(0);
    while(!layer.empty()){
        int head = layer.front();
        layer.pop_front();
        for(auto C : g[head]){
            for(auto U : C.se)
                if(was.find({U , C.fi}) == was.end())
                    dfs(head , U , C.fi);
        }
    }
    if(d[n - 1] == inf)cout << -1;
    else
    cout << d[n - 1] << '\n';
    return 0;
}


Measured memory_bytes: 80384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("atcoder-problems/abc065_a.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v) \
rep(l, v.size()) { cout << v[l] << " "; } \
cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  ll X, A, B;
  cin >> X >> A >> B;

  string ans = "";
  ll x = B - A;
  if (x <= 0) {
    ans = "delicious";
  } else if (x >= X + 1) {
    ans = "dangerous";
  } else {
    ans = "safe";
  }

  cout << ans << endl;
}

Measured memory_bytes: 3656
#include<stdio.h>
int main(void){

int a,b,c,i,k=0;

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

for(i=a;i<=b;i++){
if(c%i==0){
k=k+1;
}
}
printf("%d\n",k);

return 0;
}

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return abs(a); }

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
	ll n;
	cin >> n;
	vector<ll> vs(n);
	rep(i, n) cin >> vs[i];
	ll ans = 1;
	rep(i, n) {
		ans = lcm(ans, vs[i]);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

const ll INF = 170000000000000;

int main() {
    ios::sync_with_stdio(false);

    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);

    int n;
    cin >> n;
    vector<ll> v(n + 1, 0);
    vector<ll> sp(n + 1, 0);
    for(int i = 1; i <= n; i ++) {
        cin >> v[i];
        sp[i] = v[i] + sp[i - 1];
    }

    vector<vector<ll>> dp(n + 2, vector<ll> (n + 2, INF));
    for(int i = 1; i <= n; i ++)
        dp[i][i] = 0;

    for(int len = 2; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++) {
            int j = i + len - 1;
            for(int k = i; k < j; k ++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sp[j] - sp[i - 1]);
        }
    cout << dp[1][n];

    return 0;
}


Measured memory_bytes: 1536
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{

    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int M = int.Parse(s[1]);

            int maxSW = (int)Math.Pow(2, N);

            int[] count = new int[M];
            int[] mask = new int[M];

            for (int i = 0; i < M; i++)
            {
                s = Console.ReadLine().Split(' ');

                int K = int.Parse(s[0]);

                for (int j = 0; j < K; j++)
                {
                    mask[i] |= (1 << (int.Parse(s[j + 1]) -1));
                }
            }

            s = Console.ReadLine().Split(' ');
            for (int i = 0; i < M; i++)
            {
                count[i] = int.Parse(s[i]);
            }

            int ans = 0;
            for (int i = 0; i < maxSW; i++)
            {
                bool isOn = true;
                for (int j = 0; j < M; j++)
                {
                    int r = i & mask[j];
                    if(count[j] != bitCount(r) % 2)
                    {
                        isOn = false;
                        break;
                    }
                }

                if (isOn)
                {
                    ans++;
                }
            }

            Console.WriteLine(ans);
        }


        static int[] bitC = new int[]
        {
            0,1,1,2,
            1,2,2,3,
            1,2,2,3,
            2,3,3,4
        };

        static int bitCount(int i)
        {
            int c = 0;
            while(i>0)
            {
                c += bitC[i & 0x0f];
                i >>= 4;
            }

            return c;
        }
    }
}


Measured memory_bytes: 11220
#!/usr/bin/env python3
import sys
import math
Q = int(sys.stdin.readline())
A = [0]*Q
B = [0]*Q
for i in range(Q):
    A[i], B[i] = list(map(int, sys.stdin.readline().split()))


def f(a, b, d):
    """
    a, a+1, ..., b と d, d-1, ..., d-(b-a)
    積から、最大のものを返す
    """
    kosu = b-a+1
    wa = d+a
    if wa//2 < a:
        return a*d

    elif wa//2 < b:
        return b*(wa//2-b)

    else:
        return b*d-(b-a)


for i in range(Q):
    if A[i] == B[i]:
        print(2*(A[i]-1))
        continue
    a = min(A[i], B[i])
    b = max(A[i], B[i])
    # print("(A[i], B[i]) = ({},{})".format(a, b))
    c = math.ceil(math.sqrt(a*b))-1
    # print("C={}".format(c))
    if c*(c+1) < a*b:
        print(2*c-1)
    else:
        print(2*c-2)


Measured memory_bytes: 3064