akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

#define pb push_back
#define ff first
#define ss second
#define SIZE 2001
#define INF 2e9 + 9
#define BIG_INF 1e18 + 9
#define acmpIN "input.txt"
#define acmpOUT "output.txt"

//#pragma GCC optimize("Ofast")
//


int n, x, y;


int dst[SIZE][SIZE];


int ans[SIZE];

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//    freopen(acmpIN, "r", stdin);
//    freopen(acmpOUT, "w", stdout);



    cin >> n >> x >> y;
    x--;y--;
    if(x > y) swap(x, y);
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {

            int dst1 = j - i;
            int dst2 = abs(x - i) + 1;
            dst2 += abs(y - j);
            int dst3 = abs(y - i) + 1;
            dst3 += abs(x - j);
            dst[i][j] = min(dst1, min(dst2, dst3));
            ans[dst[i][j]]++;
//            cout << i + 1 << ' ' << j + 1 << ' ' << dst[i][j] << endl;
        }
    }


    for(int i = 1; i < n; i++)
    {
        cout << ans[i] << "\n";
    }




    return 0;
}


Measured memory_bytes: 15360
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <thread>
#include <chrono>

using namespace std;

int main(void){
	int a, b;
	cin >> a >> b;
	for(int i=1;i<=3;i++){
		if(a*b*i %2 == 1){
			cout << "Yes" << endl;
			exit(0);
		}
	}
	cout << "No" << endl;
	return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())

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

    ll ans=T;
    for (int i = 0; i < N-1; i++) {
        if (time[i] + T <= time[i+1]) {
            ans += T;
        }else{
            ans += time[i+1] - time[i];
        }
    }

    cout << ans << endl;
    return;
}

int main(int argc, char const* argv[])
{
    solve();
    return 0;
}


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


int main()
{
   int a,b,c;
   int min,max=0;
   cin>>a>>b>>c;

   if(a<=b)
   {
       min = a;
       max = b;
   }
   
   else
   {
     min = b;
     max = a;

   }
  

   if(c>min && c<max)
   cout<<"Yes"<<endl;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma warning(disable:4996)
#ifdef _MSC_VER
#  define __builtin_popcount __builtin_popcountll
#  define __builtin_popcountll __popcnt
#endif
#define int long long
using namespace std;
using ll = long long;
using ld = long double;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
inline void my_io() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout << fixed << setprecision(10);
}
class LazySegmentTree{
private:
	int n;
	vector<ll>node, lazy;
public:
	LazySegmentTree(vector<ll>v) {
		int sz = (int)v.size();
		n = 1; while (n < sz)n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, 0);

		for (int i = 0; i<sz; i++)node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--)node[i] = node[i * 2 + 1] + node[i * 2 + 2];
	}
	//k番目のノードについて遅延評価を行う
	void eval(int k, int l, int r) {
		//遅延配列が空でない場合、自ノード及び子ノードへの値の伝播がおこる
		if (lazy[k] != 0) {
			node[k] += lazy[k];
			//最下段かどうかのチェックをする
			//子ノードは親ノードの1/2の範囲であるため伝播させるときは半分にする
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k] / 2;
				lazy[2 * k + 2] += lazy[k] / 2;
			}

			// 伝播が終わったので、自ノードの遅延配列を空にする
			lazy[k] = 0;
		}
	}
	void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
		if (r < 0)r = n;
		

		
		//範囲外なら何もしない
		if (b <= l || r <= a) {
			eval(k, l, r);
			return;
		}
		//完全に被覆しているならば、遅延評価に値を入れた後に評価
		if (a <= l && r <= b) {
			lazy[k] += (r - l)*x;
			eval(k,l,r);//おろさないと次のelse文node[k] = node[2 * k + 1] + node[2 * k + 2];で問題が起きる node[k]を正しい値にする
		}
		//そうでないなら子ノードの値を再帰的に計算して計算済みの値をもらってくる
		else {
			// k 番目のノードに対して遅延評価を行う
			eval(k, l, r);
			//k番目のノードに対して遅延評価を行う
			add(a, b, x, 2 * k + 1, l, (l + r) / 2);
			add(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = node[2 * k + 1] + node[2 * k + 2];
		}
	}
	ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		if (b <= l || r <= a) return 0;

		// 関数が呼び出されたら評価！
		eval(k, l, r);
		if (a <= l && r <= b) return node[k];
		ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
		ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
		return vl + vr;
	}
};
signed main() {
	my_io();
	int n, q;
	cin >> n >> q;
	vector<int>a(n, 0);
	LazySegmentTree Lsegtree(a);
	for (int i = 0; i < q; i++) {
		int b;
		cin >> b;
		if (b == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			s--;
			Lsegtree.add(s, t, x);
		}
		else if(b == 1){
			int s, t;
			cin >> s >> t;
			s--;
			cout << Lsegtree.getsum(s, t) << endl;
		}
	}
	return 0;
}




Measured memory_bytes: 8692
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <tuple>

using namespace std;

typedef vector<vector<char> > Field;
typedef vector<vector<bool> > LocationMap;
typedef pair<int, int> Location;
typedef pair<Location, int> LocationLevel;
typedef queue<LocationLevel> LocationQueue;

inline int solve(int h, int w, Field &field, LocationQueue &que, LocationMap& visited) {
  /*
  cout << h << " " <<  w << " " << endl;
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cout << field[i][j];
    }
    cout << endl;
  }
  */
  LocationLevel loc_lev;
  Location loc;
  Location nloc;
  int i, j, level;
  int max_level = 0;
  int dx[4] = {-1, 1, 0, 0};
  int dy[4] = { 0, 0, 1,-1};

  while(que.size()){
    loc_lev = que.front(); que.pop();
    loc = loc_lev.first;
    level = loc_lev.second;

    for(int n = 0; n < 4; n++){
        i = loc.first  + dx[n];
        j = loc.second + dy[n];

        if (i >= 0 && i <= h - 1 && j >= 0 && j <= w -1) {
          nloc = make_pair(i,j);
          if( !visited[i][j] && (field[i][j] == '.') ){
            field[i][j] = '#';
            visited[i][j] = true;
            que.push(make_pair(nloc, level + 1));
            if( level + 1 > max_level ){ max_level = level + 1; }
          }
        }
    }
  }

  return max_level;
}

int main(int argc, char const *argv[]) {
  int h, w;
  char c;
  Field field;
  LocationQueue que;
  LocationMap visited;

  cin >> h;
  cin >> w;

  for (int i = 0; i < h; i++) {
    vector<char> row;
    vector<bool> brow;
    for (int j = 0; j < w; j++) {
      cin >> c;
      row.push_back(c);
      if (c == '#') {
        que.push(make_pair(make_pair(i, j), 0));
        brow.push_back(true);
      } else {
        brow.push_back(false);
      }
    }
    field.push_back(row);
    visited.push_back(brow);
  }

  cout << solve(h, w, field, que, visited);

  return 0;
}


Measured memory_bytes: 13712
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::terminate;
using std::string;

template<class T> inline T max(T X, T Y) {
    return X > Y ? X : Y;
}

// trace back approach
void solve() {
    string s, t; cin >> s >> t;

    int dp[s.size() + 1][t.size() + 1];
    for (int i = 0; i < s.size() + 1; ++i) {
        for (int j = 0; j < t.size() + 1; ++j) {
            dp[i][j] = 0;
        }
    }

    for (int i = 0; i < s.size(); ++i) {
        for (int j = 0; j < t.size(); ++j) {
            if (s[i] == t[j]) {
                dp[i+1][j+1] = dp[i][j] + 1;
            }
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j]);
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
        }
    }

    // for (int i = 0; i < s.size(); ++i) {
    //     for (int j = 0; j < t.size(); ++j) {
    //         if (j != t.size() - 1) cout << dp[i+1][j+1] << " ";
    //         else cout << dp[i+1][j+1] << endl;
    //     }
    // }

    string ans = "";
    int i, j; i = s.size() - 1; j = t.size() - 1;
    while (i >= 0 && j >= 0 && dp[i+1][j+1] != 0) {
        if (dp[i+1][j+1] == dp[i+1][j]) {
            --j;
        } else if (dp[i+1][j+1] == dp[i][j+1]) {
            --i;
        } else if (dp[i+1][j+1] != dp[i+1][j] && dp[i+1][j+1] != dp[i][j+1]) {
            ans.insert(ans.begin(), s[i]);
            --i; --j;
        } else {
            // It's not reachable
        }
    }

    cout << ans << endl;
}

int main() {

#ifdef DEV
    std::ifstream in("input");
    cin.rdbuf(in.rdbuf());

    int t; cin >> t;
    for (int x = 1; x <= t; ++x) {
        solve();
    }
#else
    solve();
#endif

    return 0;
}


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

using namespace std;

/* MEMO
 * スライド最小値(スライドしてくやつ)
 * BIT(セグ木の進化系みたいなやつ)
 * DP(ダイナミックP)
 * ダイクストラ(グラフ)
 * 座標圧縮(zip)
 * イモス法(なんかドンッてするやつ)
 */

// アルファベットから整数へ ( 小文字 -> [0, 26), 大文字 -> [32, 58) )
#define table_of_alphabet_to_number(t) map<char, int> t = { make_pair('a',  0) , make_pair('b',  1) , make_pair('c',  2), make_pair('d',  3), make_pair('e',  4), make_pair('f',  5), make_pair('g',  6), make_pair('h',  7), make_pair('i',  8), make_pair('j',  9), make_pair('k', 10), make_pair('l', 11), make_pair('n', 12), make_pair('m', 13), make_pair('o', 14), make_pair('p', 15), make_pair('q', 16), make_pair('r', 17), make_pair('s', 18), make_pair('t', 19), make_pair('u', 20), make_pair('v', 21), make_pair('w', 22), make_pair('x', 23), make_pair('y', 24), make_pair('z', 25), make_pair('A',  0 + 32), make_pair('B',  1 + 32), make_pair('C',  2 + 32), make_pair('D',  3 + 32), make_pair('E',  4 + 32), make_pair('F',  5 + 32), make_pair('G',  6 + 32), make_pair('H',  7 + 32), make_pair('I',  8 + 32), make_pair('J',  9 + 32), make_pair('K', 10 + 32), make_pair('L', 11 + 32), make_pair('N', 12 + 32), make_pair('M', 13 + 32), make_pair('O', 14 + 32), make_pair('P', 15 + 32), make_pair('Q', 16 + 32), make_pair('R', 17 + 32), make_pair('S', 18 + 32), make_pair('T', 19 + 32), make_pair('U', 20 + 32), make_pair('V', 21 + 32), make_pair('W', 22 + 32), make_pair('X', 23 + 32), make_pair('Y', 24 + 32), make_pair('Z', 25 + 32) }

// 多次元 std::array
template <typename T, std::size_t... Ns>
    struct index_reverse_for_array;
template <typename T, std::size_t N, std::size_t... Ns>
    struct index_reverse_for_array<T, N, Ns...> { using type = std::array< typename index_reverse_for_array<T, Ns...>::type, N>; };
template <typename T, std::size_t N>
    struct index_reverse_for_array<T, N> { using type = std::array<T, N>; };
template <class T, std::size_t... Ns> using mul_array = typename index_reverse_for_array<T, Ns...>::type;

// 型確認用
template <class T> struct template_assert;


int main() {
    string mojire2;
    cin >> mojire2;

    for (int i = 0; i < mojire2.size(); i++)
        if (mojire2[i] == '/') {
            if (mojire2[i+1] == '0' && (mojire2[i+2] == '1' || mojire2[i+2] == '2' || mojire2[i+2] == '3' || mojire2[i+2] == '4'))
                cout << "Heisei" << endl;
            else
                cout << "TBD" << endl;
            break;
        }

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>

using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::vector;
using std::queue;
using std::priority_queue;
using std::greater;
using std::max;
using std::min;

using lli = long long int;
using ulli = unsigned long long int;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

string str, ans;

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

	cin >> str;
	for(int i = 0; i < str.size(); i++){
		if(i % 2 == 0){
			ans+=str[i];
		}
	}

	cout << ans;
  return 0;
}


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

// {
#define debug(var)  do{ std::cout << #var << " : "; view(var); }while(0)
using ll = long long;
using ld = long double;
inline int num (const std::string& S, int idx) noexcept { return S.at(idx) - '0'; }
inline int ctoi(char c) noexcept { return c - '0'; }
inline bool isNumber(char c) noexcept { return ('0'<c && c<'9'? true : false); }
inline int safeCtoi(char c) { if(isNumber(c)) { return ctoi(c); } else { throw 1; } }
inline char itoc(int i) noexcept { return i + '0'; }
inline unsigned int bitMask(int i) noexcept { return (1 << i); }
inline bool isTrue(unsigned int bit, int i) noexcept { return bit & bitMask(i); }
inline bool isEven(int num) noexcept { return !num%2; }
inline bool isOdd(int num) noexcept { return num%2; }
template<typename T> inline short sgn(T num) noexcept { return (num==0? 0 : (num>0? 1 : -1) ); }
template<typename T> inline bool isZero(T num) noexcept { return (num==0? true : false); }
template<typename T> inline bool isPositive(T num) noexcept { return (num>0? true : false); }
template<typename T> inline bool isNegative(T num) noexcept { return (num<0? true : false); }
template<typename T> void view(T e) noexcept { cout << e; }
template<typename T> void view(std::vector<T> v) noexcept { for(const auto& e : v) cout << e << " "; }
template<typename T> void view(std::vector<std::vector<T>> vv) noexcept { for(const auto& v : vv) view(v); }
//}


int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	long long a, v, b, w, t;
	cin >> a >> v >> b >> w >> t;
	if( abs(a-b) <= (v-w)*t ){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	return 0;
}


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

int main() {
	string s;
	cin >> s;
	ll ans = 0;
	while (s.length()>=2) {
		if (s.at(0) == 'W')s = s.substr(1);
		else break;
	}
	if (s.length() == 1) {
		cout << 0 << endl;
		return 0;
	}
	ll w = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s.at(i) == 'W') {
			ans += i;
			w++;
		}
	}
	ans -= w * (w - 1) / 2;
	cout << ans << endl;
}

Measured memory_bytes: 772
#include<cstdio>
#include<cmath>

//#include<iostream>
using namespace std;

int main(){
	int n;
	float x1, y1, x2, y2, x3, y3, a1,b1,c1,a2,b2,c2;
	float xc, yc, r;

	scanf("%d", &n);
	while(n--){
		scanf("%f%f%f%f%f%f",&x1, &y1, &x2, &y2, &x3, &y3);
	
//	http://pegasus.infor.kanazawa-it.ac.jp/~koblab/home/d1504310/acm/asia/1997/97_C_Minimal_Circle.html

    a1=(x2-x1)*2;
    b1=(y2-y1)*2;
    c1=x1*x1-x2*x2+y1*y1-y2*y2;
    a2=(x3-x1)*2;
    b2=(y3-y1)*2;
    c2=x1*x1-x3*x3+y1*y1-y3*y3;
    xc=(b1*c2-b2*c1)/(a1*b2-a2*b1);
    yc=(c1*a2-c2*a1)/(a1*b2-a2*b1);
    r=sqrt((x1-xc)*(x1-xc)+(y1-yc)*(y1-yc));
    printf("%.3f %.3f %.3f\n",xc,yc,r);
		
	}
	return 0;
}

Measured memory_bytes: 1080
#include<cmath>
#include<bits/stdc++.h>
#define MAX(a,b) (a>b? a:b)
#define MIN(a,b) (a>b? b:a)
#define rep(i,n) for(lint i=0;i<(lint)(n);i++)
#define repr(i,n) for(lint i=(lint)(n);i>0;--i)
#define reps(i,a,b) for(lint i=a;i<=(lint)(b);i++)
typedef long long lint;
typedef long double ld;
using namespace std;
const ld PI = acos(-1.0);

int main(){
    char s[4] = { 'A', 'C', 'G', 'T' };
    char b;
    cin >> b;
    rep(i,4) if(b==s[i]) cout << s[3-i] << endl;
	return 0;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
	int N; cin >> N;
	vector<ll> a(N);
	rep(i, N) cin >> a[i];

	int ans = INF;
	REP(i, -100, 101) {
		int cst = 0;
		rep(j, N) {
			cst += (a[j] - i) * (a[j] - i);
		}
		ans = min(ans, cst);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<ll,ll>P;
#define MAX 1e15
struct edge{int to,cost;};
//_________________________________________________
ll V,E,r;
vector<P>G[100000];
ll d[100000];
bool used[100000];

int main() {
  cin >>V;
  cin >>E>>r;
  rep(i,V){d[i]=MAX; used[i]= false;}
  d[r]=0;
  //入力
  int a,b,c;//a→ｂのコストがｃ。
  for(int i=0;i<E;i++){
    cin >>a>>b>>c;
   	G[a].push_back(P(b,c));
  
  }
  
  
  
  priority_queue<P,vector<P>,greater<P>> PQ;
  PQ.push(P(0,r));//P(x,y)についてtyoutenｒからｙへの距離がｘである。
  while(!PQ.empty()){
   P f=PQ.top();PQ.pop();
    int u= f.second;
    used[u]=true;
    if(d[u]<f.first) continue;//すでにd[u]にあるやつのほうが小さいなら更新不要
    
    for(int j=0;j<G[u].size();j++){
     	int v=G[u][j].first;
      	if(used[v]){continue;}
      	if(d[v]>d[u]+G[u][j].second){d[v]=d[u]+G[u][j].second;
          PQ.push(P(d[v],v));
          
        }
    }  //forno
  } //whileno
  
  rep(i,V){
  if(d[i]!=MAX){cout<<d[i]<<endl;}
  else{cout<<"INF"<<endl;}
  
  }
  
}


Measured memory_bytes: 19452
package main

import (
	"fmt"
	"math"
)

const MAX = 50

type INT int64

func main() {
	solve()
}

func solve() {
	n, s := input()
	if n == s {
		fmt.Println(n + 1)
		return
	}
	for i := INT(2); i <= INT(math.Sqrt(float64(n))); i++ {
		if s == f(i, n) {
			fmt.Println(i)
			return
		}
	}
	for i := INT(math.Sqrt(float64(n))); i > 0; i-- {
		b := (n-s)/i + 1
		if INT(math.Sqrt(float64(n))) < b && s == f(b, n) {
			fmt.Println(b)
			return
		}
	}
	fmt.Println(-1)
	return
}

func input() (n, s INT) {
	fmt.Scan(&n)
	fmt.Scan(&s)
	return n, s
}

func f(b, n INT) INT {
	if n < b {
		return n
	}
	return f(b, n/b) + n%b
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <stdio.h>
#include <string.h>
#include <typeinfo>
#include <memory>
#include <deque>
#include <iomanip>
#include <set>
using namespace std;

typedef long long lld;

#include <iostream>

using namespace std;


int main()
{
    int k,t;
    cin>>k>>t;
    vector<int> a(t + 1,0);
    for(int i = 1; i <= t; ++i){
        cin>>a[i];
    }
    vector<bool> f(k/2 + 1,false);
    f[0] = true;
    for(int i = 1; i <= t; ++i){
        for(int j = k/2; j >= a[i]; --j){
            f[j] = (f[j] || f[j-a[i]]);
        }
    }
    int tmp = 0;
    for(int j = k/2; j >= 0; --j){
        if(f[j]){
            tmp = j;
            break;
        }
    }
    cout<<max(0, k - tmp*2 - 1)<<endl;
    return 0;
}






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

int main(){
    double W, H, x, y;
    double ans1;
    bool ans2;
    cin >> W >> H >> x >> y;
    ans1 = W*H/2.0;
    ans2 = (W==2*x && H==2*y);
    
    cout << ans1 << " "<<ans2<< endl;	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define mp(x, b) make_pair(a, b)
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = (1e9 + 7);
using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
ll dp[100010];
ll gcd(ll x, ll y){
  return y == 0 ? x : gcd(y, x % y);
}
ll lcg(ll x, ll y){
  return x * y / gcd(x, y);
}
map<ll, ll> factor(ll n){
  map<ll, ll> ans;
  ll a = 2;
  while (n >= a * a){
    if (n % a == 0){
      ans[a]++;
      n /= a;
    }
    else a++;
  }
  ans[n]++;
  return ans;
}
template<class T> inline bool chmin(T& a, T b){
  if (a > b){
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b){
  if (a < b){
    a = b;
    return true;
  }
  return false;
}

int main(){
  cout << fixed << setprecision(15);
  ll ans;
  
  ll n; cin >> n;
  ans = n * (n - 1) / 2;
 
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int N,M;cin >> N >> M;
  int n = 1<<N;
  //鍵集合Sにするのに必要な最小のお金
  int dp[2][n];
  int *prv,*nxt;
  prv = dp[0];
  nxt = dp[1];
  rep(i,n){
    prv[i] = MAX_I;
    nxt[i] = MAX_I;
  }
  prv[0] = 0;

  rep(i,M){
    int a,b;cin >> a >> b;
    int X = 0;
    rep(j,b){
      int c;cin >> c;--c;
      X |= 1<<c;
    }
    rep(S,n){
      nxt[S] = min(prv[S],nxt[S]);
      if(prv[S]==MAX_I)continue;
      int S_ = S|X;
      if(S_==S)continue;
      nxt[S_] = min(nxt[S_],prv[S]+a);
    }
    swap(prv,nxt);
  }
  swap(prv,nxt);
  if(nxt[n-1] == MAX_I)cout << -1 << endl;
  else cout << nxt[n-1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

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

	cin >> N;
	vector<int>v(N + 1);
	for (auto &i : v)cin >> i;
	vector<long long int>mx(N + 1, 1);
	for (int i = 1; i <= N; i++) {
		if (mx[i - 1] < v[i - 1]) {
			cout << -1 << endl;
			return 0;
		}
		mx[i] = mx[i - 1] - v[i - 1];
		mx[i] <<= 1;
		mx[i] = min(mx[i], MOD*MOD);
	}
	if (mx[N] < v[N]) {
		cout << -1 << endl;
		return 0;
	}
	long long int ans = 0;
	long long int num = 0;
	for (int i = N; i >= 0; i--) {
		num += v[i];
		num = min(num, mx[i]);
		ans += num;
	}
	cout << ans << endl;
}

Measured memory_bytes: 4520
#include "bits/stdc++.h"
#define REP(i, a, n) for(int i=a; i<n; i++)
using namespace std;

int n, k;
int a[100001];
int main() {
    cin>>n>>k;
    REP(i, 0, n) cin>>a[i];

    int ans=0;
    int idx;
    REP(i, 0, n){
        if(a[i]==1) idx=i;
    }

    int tmp=idx;
    int add=0;
    while(tmp>0){
        ans++;
        tmp-=(k-1);
    }
    add+=0-tmp;

    tmp=n-idx-1;
    while(tmp>0){
        ans++;
        tmp-=(k-1);
    }
    add+=0-tmp;

    if(add>=k-1) ans--;
  
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 640
S=input()
# S = "".join(["RL" for i in range((10**5)//2)])

is_r = True
odd_cnt,even_cnt = 0,0
is_odd = False
l_is_odd = None
l_pos = None
result = []
for i,s in enumerate(S):
  is_odd = not is_odd
  if is_r and s=="R":
    pass
  elif is_r and s=="L":
    is_r = False
    l_is_odd = is_odd
    l_pos = i
  elif not is_r and s=="L":
    pass
  elif not is_r and s=="R":
    is_r = True
    result[l_pos] = odd_cnt if l_is_odd else even_cnt
    result[l_pos-1] = even_cnt if l_is_odd else odd_cnt
    odd_cnt,even_cnt = 0,0
  else:
    raise Exception()
  if is_odd:
    odd_cnt += 1
  else:
    even_cnt += 1
  result.append(0)

result[l_pos] = odd_cnt if l_is_odd else even_cnt
result[l_pos-1] = even_cnt if l_is_odd else odd_cnt
odd_cnt,even_cnt = 0,0

print(" ".join(map(
  lambda x:str(x),
  result)))


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

int n;
vector<string> s(100);
int m;
vector<string> t(100);
map<string, int> mapp;

int main(){
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s.at(i);
  }
  cin >> m;
  for(int i=0;i<m;i++){
    cin >> t.at(i);
  }
  for(int i=0;i<n;i++){
    if(mapp.count(s.at(i))) mapp[s.at(i)]+=1;
    else mapp[s.at(i)]=1;
  }
  for(int i=0;i<m;i++){
    if(mapp.count(t.at(i))) mapp[t.at(i)]-=1;
    else mapp[t.at(i)]=-1;
  }
  int max_yen=0;
  for(int i=0;i<n;i++){
    int yen = mapp[s.at(i)];
    if(yen>max_yen) max_yen = yen;
  }
  for(int i=0;i<m;i++){
    int yen = mapp[t.at(i)];
    if(yen>max_yen) max_yen = yen;
  }
  cout << max_yen << endl;
}

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

def main():
    N,M = map(int, input().split())
    A = []
    for _ in range(M):
        A.append(list(map(int, input().split())))
    p1 = [0]*N
    for a in A:
        if a[0] == 1:
            p1[a[1]] = 1
    for a in A:
        if a[1] == N and p1[a[0]]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()


Measured memory_bytes: 53320
from collections import deque 
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=deque([(0,-1)])
#print(que)
while que:
    now, pre=que.pop()
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

print(" ".join(map(str, X)))

Measured memory_bytes: 65640
N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
B = [0]*N
for j in range(Q):
    B[A[j]-1] += 1
for k in range(N):
    if B[k] <= Q-K:
        print("No")
    else:
        print("Yes")

Measured memory_bytes: 56024
#include <bits/stdc++.h>
#define MAX 100005
using namespace std;

typedef long long ll;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	#ifdef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n, k;

	cin>>n>>k;

	ll res = (ll) (n / k);
	ll ans = 0;

	ans += res;
	ans += ((res * (res - 1)) / 2) * 6;
	ans += ((res * (res - 1) * (res - 2)) / 6) * 6;

	if(k % 2 == 0){
		res = n / (k / 2) - res;
		ans += res;
		ans += ((res * (res - 1)) / 2) * 6;
		ans += ((res * (res - 1) * (res - 2)) / 6) * 6;
	}

	cout<<ans<<endl;

	return 0;
}

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

#define ll long long
#define pb push_back
#define mp make_pair

void solve() {

	ll n;
	cin >> n;
	ll a[n];
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}

	if(n == 2){
		cout << a[1] << " " << a[0] << endl; 
		return;
	}

	
	ll aa = 0;
	//cout << aa;
	ll b;
	for(int i = 1;i < n;i++){
		aa = aa^a[i];
	}
	cout << aa;

	for(int i = 1;i < n;i++){
		b = a[i]^a[i-1]^aa;
		cout << " " << b;
		aa = b;

	}
	





}


int main()
{

	ios::sync_with_stdio(0);
	cin.tie(0);

	ll T;
	T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}




}


Measured memory_bytes: 5192
#include <stdio.h>
#define N 100005
#define NIL -1
 
typedef struct{
  int p,s,deg,def,h,l,r;
}Node;
Node T[N];

int max(int a, int b){
    if(a>b) return a;
    else return b;
}

int depth(int id){
  int tmp;
  tmp = id;
  for(;;){
    if(T[tmp].p!=NIL) T[id].def += 1;
    else  break;
    tmp=T[tmp].p;
  }    
  return T[id].def+1; 
}

int height(int id){
    if(T[id].h != -1)                   return T[id].h;
    if(T[id].l == -1 && T[id].r == -1)  T[id].h = 0;
    else if(T[id].l == -1)              T[id].h = height(T[id].r) + 1;
    else if(T[id].r == -1)              T[id].h = height(T[id].l) + 1;
    else                                T[id].h = max( height(T[id].l), height(T[id].r) ) + 1;
    return T[id].h;
}

int main(void){
  int n, k, z;
  int id,tmp, max, num;
 
  scanf("%d", &n);
  for(int i = 0 ; i < n ; i++)
    T[i].p = T[i].s = T[i].deg = T[i].def = T[i].h =NIL;
  
  for(int i = 0 ; i < n ; i++){
    scanf("%d %d %d",&z, &id, &k);
    T[id].p = T[k].p = z;
    T[k].s = id; T[id].s = k;
    if(id == NIL && k == NIL)       T[z].deg = 0;
    else if(id != NIL && k != NIL)  T[z].deg = 2;
    else                            T[z].deg = 1;
    
    T[z].l = id; T[z].r = k;
  }

  for(int i=0;i<n;i++){
    printf("node %d: parent = %d, ",i,T[i].p);
    printf("sibling = %d, ",T[i].s);
    printf("degree = %d, ",T[i].deg);
    printf("depth = %d, ",depth(i));
    printf("height = %d, ",height(i));
    if(T[i].p==-1) T[i].deg=-1;
    switch(T[i].deg){
      case -1: printf("root");          break;
      case  0: printf("leaf");          break;
      case  1: printf("internal node"); break;
      case  2: printf("internal node"); break;
    }
    printf("\n");
  }
	return 0;
}




Measured memory_bytes: 2120
M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()

Measured memory_bytes: 27548
class CantWaitForHoliday:
    def __init__(self):
        self.W =['MON','TUE','WED','THU','FRI','SAT','SUN']
    
    def calculate(self, S):
        if S == 'SUN':
            return 7
        n = self.W.index(S)
        return 6 - n
if __name__ == '__main__':
    S = input()
    CW = CantWaitForHoliday()
    result = CW.calculate(S)
    print(str(result))
    

Measured memory_bytes: 2940
while True:
    w, h = map(int, raw_input().split())
    if w | h == 0:
        break
    dp = [[[0] * (w + 1) for _ in xrange(h + 1)] for _ in xrange(4)]    
    #0:u -> u, 1: u -> r, 2: r -> u, 3: r -> r
    dp[0][1][0] = dp[3][0][1] = 1
    for y in xrange(h):
        for x in xrange(w):
            dp[0][y + 1][x] += dp[0][y][x] + dp[2][y][x]
            dp[1][y][x + 1] += dp[0][y][x]
            dp[2][y + 1][x] += dp[3][y][x]
            dp[3][y][x + 1] += dp[1][y][x] + dp[3][y][x]
    print sum(dp[i][h-1][w-1] for i in xrange(4)) % 100000

Measured memory_bytes: 5816
package main

import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)

type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

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

func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func solve(io *Io) {
	a := io.NextInt()
	b := io.NextInt()

	vals := []int{a + b, a-b, a * b}
	ans := vals[0]
	for _, i := range(vals) {
		if ans < i {
			ans = i
		}
	}

	io.PrintLn(ans)
}

func main() {
	io := NewIo()
	defer io.Flush()

	solve(io)
}

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

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;

    Graph G(N);
    for (int i=0; i<=N-2; i++) {
        G[i].push_back(i+1);
        G[i+1].push_back(i);
    }
    G[X-1].push_back(Y-1);
    G[Y-1].push_back(X-1);

    int accum[N] = {};
    rep(k, N) { // kが出発点
        queue<int> que;
        vector<int> dist(N, -1);
        dist[k] = 0;
        que.push(k);

        while (!que.empty()) {
            int v = que.front();
            que.pop();

            for (int nv : G[v]) {
                if (dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                accum[dist[nv]]++;
                que.push(nv);
            }
        }
    }
    
    for (int k=1; k<=N-1; k++) cout << accum[k] / 2 << endl; 

    return 0;
}



Measured memory_bytes: 384
n = int(input())
nums = []
for i in range(3, n + 1):
  if i % 3 == 0 or i % 10 == 3 or '3' in str(i):
      #print('',i,end='')
      nums.append(i)
for i in nums:
    print('',i,end='')
print()

Measured memory_bytes: 7012
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
#include <stack>
#include <iomanip>
#include <limits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;

using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

typedef priority_queue<ll> PQ_HIGH;
typedef priority_queue<ll,VL,greater<ll>> PQ_LOW;//昇順

//A 65
//a 97
//pairの比較関数(昇順)
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
//降順
bool compare_by_b_high(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){
  int N;cin>>N;
  VI a(N);
  PQ_HIGH data;
  REP(i,N){
    cin>>a[i];
    data.push(a[i]);
  }
  for(int i=0;i<N;i++){
    if(data.top()!=a[i]){
      cout<<data.top()<<endl;
    }else{
      int tmp=data.top();
      data.pop();
      cout<<data.top()<<endl;
      data.push(tmp);
    }
  }
}

Measured memory_bytes: 4080
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll c[30],s[400][30];

int main()
{
	int D;
	cin >> D;
	rep(i,26)
	{
		cin >> c[i];
	}
	rep(i,365)
	{
		rep(j,26)
		{
			cin >>s[i][j];
		}
	}
	rep(i,365)
	{
		cout << "1" << endl;
	}
	return 0;
}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    map<int,int> m;
    for(int i=0; i<n; i++){
        cin>>a[i];
        m[a[i]]++;
    }
    
    vector<map<int,int>> yakusu(n);
    for(int i=0; i<n; i++){
        for(int j=1; j<sqrt(a[i])+1; j++){
            if(a[i]%j==0){
                yakusu[i][j]++;
                yakusu[i][a[i]/j]++;
            }
        }
    }
    int ans=0;
    for(int i=0; i<n; i++){
        bool find=false;
        bool used=false;
        for(auto j:yakusu[i]){
            if(a[i]!=j.first&&m[j.first]>0){
                find=true;
            }else if(a[i]==j.first&&m[j.first]>1){
                find=true;
            }
        }
        if(!find) ans++;
    }
    cout<<ans<<endl;

}


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

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

	for(int a, b; cin >> a >> b && a;) {
		const int change = b - a;
		const int num100 = change % 500 / 100;
		const int num500 = change % 1000 / 500;
		const int num1000 = change / 1000;
		cout << num100 << " " << num500 << " " << num1000 << endl;
	}

	return EXIT_SUCCESS;
}

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

using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;

int32_t main() {
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall
    oneforall


        
    ini(n);
    ini(n1);
    ini(k);
    ins(a);
    int dp[n+1];
    int dp1[n+1];
    dp[0] = 0;
    dp1[0] = 0;
    int last = -INF;
    FOR(i,1,n+1){
        if(a[i-1] == 'x')dp[i] = dp[i-1];
        else{
            if(last+k<i){
                last = i;
                dp[i] = dp[i-1]+1;
            }
            else{
                dp[i] = dp[i-1];
            }
        }
    }
    //FOR(i,1,n+1)out(dp[i]);
    reverse(all(a));
    last = -INF;
    FOR(i,1,n+1){
        if(a[i-1] == 'x')dp1[i] = dp1[i-1];
        else{
            if(last+k<i){
                last = i;
                dp1[i] = dp1[i-1]+1;
            }
            else{
                dp1[i] = dp1[i-1];
            }
        }
    }
    //FOR(i,1,n+1)out(dp[i]);
    reverse(all(a));
    FOR(i,0,n){
        if(a[i] == 'o' and dp[i]+dp1[n-i-1]+1 == n1){
            out(i+1);
        }
    }


    return 0;
}



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

#define int long long

const int N = 111;
const int mod = 1e9 + 7;

namespace {
  int add(int x) {return (x >= mod) ? x - mod : x;}
  int sub(int x) {return (x < 0) ? x + mod : x;}
  void Add(int &x, int y) {x = add(x + y);}
  void Sub(int &x, int y) {x = sub(x - y);}
}

int Pow(int x, int y) {
  int res = 1;
  for(; y; y >>= 1, x = x * x % mod) {
    if(y & 1) {
      res = res * x % mod;
    }
  }
  return res;
}

int n, H[N], dp[N][N][2][2][2];
int Min[N][N];

int ans = 1;

bool vis[N][N];

int get(int l, int r) {
  int h = 2e9;
  for(int i = l; i <= r; ++ i) h = min(h, H[i]);
  return h;
}

void solve(int l, int r) {
  //cerr << l <<' ' << r << endl;
  if(vis[l][r]) return;
  vis[l][r] = 1;
  if(l == r) {
    dp[l][r][1][1][0] = dp[l][r][0][0][0] = 1;
    return;
  }
  if(l > r) {
    return;
  }
  int h = 2e9;
  for(int i = l; i <= r; ++ i) {
    h = min(h, H[i]);
  }
  int who = 0;
  for(int i = l; i <= r; ++ i) if(H[i] == h) who = i;
  //cerr << l <<" " << r << " " << who << endl;
  solve(l, who - 1);
  solve(who + 1, r);
  if(l > who - 1) {
    //cerr << l <<" " << r <<" " << "in" << endl;
    for(int a = 0; a < 2; ++ a) {
      for(int b = 0; b < 2; ++ b) {
        for(int c = 0; c < 2; ++ c) {
          for(int d = 0; d < 2; ++ d) {
            Add(dp[l][r][d][b][(d == a) || c],
                dp[who + 1][r][a][b][c] * Pow(2 - c, get(who + 1, r) - h) % mod);
          }
        } 
      }
    }
    //cerr << l <<" " << r << " " << "out" << endl;
    return;
  }
  if(who == r) {
    //cerr << l <<" " << r << " in" << endl;
    for(int a = 0; a < 2; ++ a) {
      for(int b = 0; b < 2; ++ b) {
        for(int c = 0; c < 2; ++ c) {
          for(int d = 0; d < 2; ++ d) {
            Add(dp[l][r][a][d][(d == b) || c],
                dp[l][who - 1][a][b][c] * Pow(2 - c, get(l, who - 1) - h) % mod);
          }
        }
      }
    }
      //cerr << l <<" " << r <<" out" << endl;
    return;
  }
  //cerr << l << " " << r <<" in" << endl;
  for(int a = 0; a < 2; ++ a) {
    for(int b = 0; b < 2; ++ b) {
      for(int c = 0; c < 2; ++ c) {
        for(int d = 0; d < 2; ++ d) {
          for(int e = 0; e < 2; ++ e) {
            for(int f = 0; f < 2; ++ f) {
              for(int g = 0; g < 2; ++ g) {
                Add(dp[l][r][a][f][(d == b) || (d == e) || c || g],
                    dp[l][who - 1][a][b][c] * dp[who + 1][r][e][f][g] % mod * Pow(2 - c, get(l, who - 1) - h) % mod * Pow(2 - g, get(who + 1, r) - h) % mod);
              }
            }
          }
        }
      }
    }
  }
  //cerr << l << " " << r <<" out" << endl;
  return;
}

main() {
  cin >> n;
  int h = 2e9;
  for(int i = 1; i <= n; ++ i) cin >> H[i], h = min(h, H[i]);
  solve(1, n);
  //cerr << "HERE" << endl;
  int ans = 0;
  for(int a = 0; a < 2; ++ a)
    for(int b = 0; b < 2; ++ b)
      for(int c = 0; c < 2;++ c)
        Add(ans, dp[1][n][a][b][c] * Pow(2 - c, h - 1) % mod);
  
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
using namespace std;
#include<string>
#include<stack>
#include<string.h>
#include<memory.h>
#include<algorithm> 
#include<vector>
int a[4][103];
int dp[4][103];
int main()
{
	int i,j,n;
	cin>>n;
	for(i=1;i<=2;i++)
		for(j=1;j<=n;j++)
		{
			cin>>a[i][j];
			dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i][j-1]);
		 } 
	cout<<dp[2][n]<<endl;
	
	
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

vector<pair<long long, long long> > prime_factorize(long long N) {
	vector<pair<long long, long long> > res;
	for (long long a = 2; a * a <= N; ++a) {
		if (N % a != 0) continue;
		long long ex = 0; // 指数

		// 割れる限り割り続ける
		while (N % a == 0) {
			++ex;
			N /= a;
		}

		// その結果を push
		res.push_back({ a, ex });
	}

	// 最後に残った数について
	if (N != 1) res.push_back({ N, 1 });
	return res;
}

int main() {
	ll n, p;
	cin >> n >> p;
	const auto &res = prime_factorize(p);
	ll ans = 1;
	for (auto s : res) {
		ans *= pow(s.first, s.second / n);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4040
using System;
using System.Collections.Generic;
using System.Linq;
using Console = System.Console;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var r = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = r[0];
            var K = r[1];
            var ret = Console.ReadLine().Split().Select(long.Parse).OrderByDescending(x => x).Skip(K).Sum();
            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 38016
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull solve (vector<int> x, int n) {
  ull ans = 0;
  for (int i = 0; i < x.size(); i++) ans += (x.at(i) - n) * (x.at(i) - n);
  return ans;
}

int main(){
  int n;
  cin >> n;
  vector<int> x(n);
  for (int i = 0; i < n; i++) cin >> x.at(i);
  
  ull min_val = 10000000000;
  for (int i = 0; i < 101; i++) {
    ull ans = solve(x, i);
    min_val = min(min_val, ans);
  }
  cout << min_val;
  return 0;
}



Measured memory_bytes: 256
# seishin.py
from math import sqrt
Q = int(input())
for i in range(Q):
    a, b = map(int, input().split())
    if not a < b:
        a, b = b, a
    if a == b or a+1 == b:
        print(2*a-2)
        continue
    c = int(sqrt(a*b))
    if c**2 == a*b:
        c -= 1
    if c*(c+1) >= a*b:
        print(2*c-2)
        continue
    print(2*c-1)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int H=scan.nextInt();
        int W=scan.nextInt();
        int K=scan.nextInt();

        int v[]=new int[H];
        int h[]=new int[W];
        int p=0;
        int k=0;
        int c[][]=new int[H][W];
        for(int i=0;i<H;i++){ String L=scan.next();
            for(int j=0;j<W;j++){

                if (L.substring(j,j+1).equals("#")){
                    v[i]=v[i]+1;
                    h[j]=h[j]+1;
                    c[i][j]=1;
               k++; }
            }

        }
int f=0;
        for (int iii = 0; iii < (1 << H); iii++) {

            for (int ii = 0; ii < (1 << W); ii++) {
            int S = k;
            f=0;
            for (int j = 0; j < H; j++) {

                if ((1 & iii >> j) == 1) {
                    S = S -v[j];
                }


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

                        if ((1 & ii >> i) == 1&&f==0) {
                            S = S - h[i];}

                        if (((1 & ii >> i) == 1)&&((1 & iii >> j) == 1)&&(c[j][i]==1)){S++;}
                    }
                    f=1;
              }

                if (S==K){p++;}
            }

        }


        System.out.println(p);
    }
}


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


int main() {
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    vector<int> p;
    p.push_back(a);
    p.push_back(b);
    p.push_back(c);
    p.push_back(d);
    p.push_back(e);
    rep(i, 5) {
        if (p[i] == 0) {
            cout << i +1<< endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main(){
    char s[4];
    scanf("%s",s);
    if(s[0] == s[1]) {
        if(s[0] != s[2] && s[2] == s[3]) {
            cout << "Yes" << "\n";
        }else{
            cout << "No" << "\n";
        }
    }else if(s[0] == s[2]) {
        if(s[0] != s[1] && s[1] == s[3]) {
            cout << "Yes" << "\n";
        }else{
            cout << "No" << "\n";
        }
    }else if(s[0] == s[3]) {
        if(s[0] != s[1] && s[1] == s[2]) {
            cout << "Yes" << "\n";
        }else{
            cout << "No" << "\n";
        }
    }else{
        cout << "No" << "\n";
    }
}

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

int main(){
    ll N, K; cin >> K >> N;
    ll f;cin >> f;ll f_2 = f;
    ll m = 0;ll temp;
    for (ll i = 0; i < N-1; i++)
    {
       cin >> temp;
       if (m < temp - f) m = temp-f;
       f = temp;
    }
    if (K - (temp-f_2) > m) m = K - (temp-f_2);
    cout << K - m << endl;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
	int n;
	ll ans=1;
	cin>>n;
	lol(i,n){
		int a;cin>>a;
		if(a%2==0)ans*=2;
	}
	ll cnt=1;
	lol(i,n)cnt*=3;
	cout<<cnt-ans<<endl;
	return 0;
}


Measured memory_bytes: 256