akhauriyash/Code-Regression huggingface dataset:
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

namespace AtCoder.Probrems.Solvers.ABC117
{
    public class _C
    {
        static void Main(string[] args)
        {
            WriteLine(Solve());
        }

        static int N;
        static long[] X;
        public static long Solve()
        {
            N = int.Parse(ReadLine().Split()[0]);
            X = ReadLine().Split().Select(long.Parse).OrderBy(x => x).ToArray();
            return Distances(X).OrderBy(x => x).Take(X.Length - N).Sum();
        }

        static IEnumerable<long> Distances(long[] x)
        {
            var prev = x[0];
            for (int i = 1; i < x.Length; i++)
            {
                var current = x[i];
                yield return current - prev;
                prev = current;
            }
        }
        private const int MOD = 1000000007;
    }
}


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

int main() {
	// your code goes here
	string s1,s2;
	cin>>s1>>s2;
	int n1=s1.length(),n2=s2.length();
	int dp[n1+1][n2+1];
	for(int i=0;i<=n1;i++)
	{
	    for(int j=0;j<=n2;j++)
	    {
	        if(i==0||j==0)
	        {
	            dp[i][j]=0; continue;
	        }
	        else if(s1[i-1]==s2[j-1])
	        dp[i][j]=dp[i-1][j-1]+1;
	        else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
	    }
	}
	string ans;
    int i=n1,j=n2;
    int len=dp[n1][n2];
    while(len>0)
    {
        if(s1[i-1]==s2[j-1])
        {
            ans.push_back(s1[i-1]);
            i--; j--; len--;
        }
        else if(dp[i-1][j]>dp[i][j-1])
        i--;
        else j--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
	return 0;
}


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	int N,u,v, st=0, en = 0, di = 0;
	cin >> N;
	vector<vector<int> > neigh(N);
	forn(i, N - 1)
	{
		cin >> u >> v;
		neigh[u - 1].push_back(v - 1);
		neigh[v - 1].push_back(u - 1);
	}

	{
		vector<int> q(1, 0);
		vector<bool> used(N);
		used[0] = 1;
		forn(i, q.size())
		{
			int act = q[i];
			forn(j, neigh[act].size()) if (!used[neigh[act][j]])
			{
				q.push_back(neigh[act][j]);
				used[neigh[act][j]] = 1;
			}
		}
		st = q.back();
	}

	{
		vector<int> q(1, st);
		vector<int> used(N, -1);
		used[st] = 1;
		forn(i, q.size())
		{
			int act = q[i];
			forn(j, neigh[act].size()) if (used[neigh[act][j]] == -1)
			{
				q.push_back(neigh[act][j]);
				used[neigh[act][j]] = used[act] + 1;
			}
		}
		en = q.back();
		di = used[en];
	}

	vector<bool> dp(di + 1);
	dp[1] = true;
	dp[0] = true;
	fore(i, 2, di)
	{
		if (dp[i - 2] && dp[i - 1])
			dp[i] = false;
		else
			dp[i] = true;
	}
	
	if (dp[di])
		cout << "First\n";
	else
		cout << "Second\n";

	return 0;
}


Measured memory_bytes: 14564
#include<stdio.h>

int main(void){
	unsigned long long int n,x,a[131072],i,r=0;
	scanf("%llu%llu",&n,&x);
	for(i = 1;i <= n;i++){scanf("%llu",&a[i]);}
	for(i = 1;i < n;i++){
		if(a[i]+a[i+1] <= x){continue;}
		else if(a[i] <= x){r+=(a[i]+a[i+1]-x);a[i+1]-=(a[i]+a[i+1]-x);}
		else{r+=(a[i]+a[i+1]-x);a[i+1] = 0;}
	}
	printf("%llu\n",r);
	return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int N;

int main(){
    cin>>N;
    int dp[N],h[N];
    rep(i,N){
        cin>>h[i];
    }
    dp[0]=0;
    dp[1]=abs(h[0]-h[1]);
    repi(i,2,N){
        dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]));
    }
    out(dp[N-1]);
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include<bits/stdc++.h>
#define ll long long
#define read freopen("input","r",stdin)
#define write freopen("output","w",stdout)
#define fr first
#define sc second
#define ii pair < int , int >
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    int sum = n*2;
    int j = 0;
    for(int i=0;i<s.length();i++)
    {
        int maxx = n*2;
        int k = i;
        while(k < s.length() && j < s.length() && s[k] == t[j])
        {
            maxx--;
            k++;
            j++;
        }
        sum = min(sum,maxx);
        j = 0;
    }
    cout<<sum;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
vv vec;
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	int n,k;
	cin>>n>>k;
	vec.resize(n);
	for (int i = 0; i < k; ++i)
	{
		int d,a;
		cin>>d;
		while(d--){
			cin>>a;
			a--;
			vec[a].pb(i);
		}
	}
	int ans=0;
	for (int i = 0; i < n; ++i)
		ans+=vec[i].empty();
	cout<<ans<<"\n";
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Measured memory_bytes: 3656
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <cmath>
#include <tuple>
#include <bitset>
#include <utility>
#include <climits>
#include <iomanip>

#define push emplace_back
#define each(i, x) for (auto i=0; i < x; i++)
using ull = unsigned long long;
constexpr auto mod = 1000000007;
constexpr auto INF = ULLONG_MAX;

using namespace std;
template <typename T> inline void dump(const T& x) { cout << "[" << x << "]" << endl; }
template <typename T> inline void dump(const vector<T>& x) { for (const auto v : x) { cout << v << " "; } cout << endl; }
template <typename T> inline void sort_asc(vector<T>& x) { std::sort(x.begin(), x.end()); }
template <typename T> inline void sort_desc(vector<T>& x) { std::sort(x.begin(), x.end(), greater<T>()); }
template <typename T> inline T max_value(vector<T>& x) { return *max_element(x.begin(), x.end()); }
template <typename T> inline T min_value(vector<T>& x) { return *min_element(x.begin(), x.end()); }
template <typename T> inline T sum_value(vector<T>& x) { return accumulate(x.begin(), x.end(), 0ULL); }

int main() {
  ull a, b;
  cin >> a >> b;

  string ab = "";
  string ba = "";

  each(i, b) {
    ab += to_string(a);
  }

  each(i, a) {
    ba += to_string(b);
  }

  if (ab < ba) {
    cout << ab << endl;
  } else {
    cout << ba << endl;
  }

  return 0;
}


Measured memory_bytes: 256
/* 
   AOJ 2150
   Matshzaki Number
   2015/7/23
*/

#include<stdio.h>
#include<stdlib.h>

#define MAX_PRIME 200000
#define MAX_P 100

void make_prime_list(int *prime_list)
{
  int i, j;

  for(i = 0; i < MAX_PRIME; i++)
    {
      prime_list[i] = 1;
    }

  prime_list[0] = 0;
  prime_list[1] = 0;

  for(i = 0; i < MAX_PRIME; i++)
    {
      if(prime_list[i] == 1)
	{
	  for(j = i; i * j < MAX_PRIME && i * j > 0; j++)
	    {
	      prime_list[i * j] = 0;
	    }
	}
    }
}

void make_next_prime_list(int* prime_list, int* next_prime_list)
{
  int i, next_prime = -1;

  for(i = MAX_PRIME - 1; i >= 0; i--)
    {
      if(prime_list[i] == 1)
	{
	  break;
	}
      next_prime_list[i] = -1;
    }

  for(; i >= 0; i--)
    {
      next_prime_list[i] = next_prime;

      if(prime_list[i] == 1)
	{
	  next_prime = i;
	}
    }
}

void get_next_prime_set(int n, int* prime_list, int* next_prime_set)
{
  int i, j = 0;
  
  for(i = n + 1; i < MAX_PRIME; i++)
    {
      if(prime_list[i] == 1)
	{
	  next_prime_set[j] = i;
	  j++;
	}
    }
}

void get_sum_list(int* next_prime_set, int* sum_list, int p)
{
  int i, j, k = 0;

  for(i = 0; i < p; i++)
    {
      for(j = i; j < p; j++)
	{
	  sum_list[k] = next_prime_set[i] + next_prime_set[j];
	  k++;
	}
    }
}

int from_one_to_p_sum(int p, int n)
{
  if(p >= 1)
    {
      return from_one_to_p_sum(p - 1, n + p);
    }
  return n;
}

int sort(const void * a, const void * b)
{
  if(*(int *)a < *(int *)b)
    {
      return -1;
    }
  else if(*(int *)a == *(int *)b)
    {
      return 0;
    }
  return 1;
}

int ans_f(int n, int p, int* prime_list)
{

  /* 
     --------next_prime_set is a prime list from the prime that is next to 'n' to MAX_PRIME

     next_prime_set[0] + next_prime_set[0], nps[0] + nps[1],....nps[0] + nps[p]
     nps[1] + nps[1], nps[1] + nps[2],...nps[1] + nps[p]
     .......
     nps[p-1] + nps[p-1], nps[p-1] + nps[p]
     nps[p] + nps[p]
     
     ---------------------------------------------------------------------------------------
  */


  int i, num_of_sum_list = 0, next_prime_set[MAX_PRIME], sum_list[MAX_PRIME];
  
  get_next_prime_set(n, prime_list, next_prime_set);

  /* for(i = 0; i < 20; i++) */
  /*   { */
  /*     printf("%3d", next_prime_set[i]); */
  /*   } */
  /* printf("\n"); */

  get_sum_list(next_prime_set, sum_list, p);

  /* for(i = 0; i < 20; i++) */
  /*   { */
  /*     printf("%3d", sum_list[i]); */
  /*   } */
  /* printf("\n"); */

  num_of_sum_list = from_one_to_p_sum(p, 0);

  qsort((void *) sum_list, num_of_sum_list, sizeof(int), sort);

  /* for(i = 0; i < 20; i++) */
  /*   { */
  /*     printf("%3d", sum_list[i]); */
  /*   } */
  /* printf("\n"); */
  
  return sum_list[p - 1];
}

int main(void)
{
  int n, p, ans, prime_list[MAX_PRIME], next_prime_list[MAX_PRIME], i;

  make_prime_list(prime_list);
  //make_next_prime_list(prime_list, next_prime_list);

  while(1)
    {
      scanf("%d %d", &n, &p);
      if(n == -1 && p == -1)
	{
	  break;
	}
      ans = ans_f(n, p, prime_list);
      printf("%d\n", ans);
    }
  return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  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;
  }
};

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  vector<vector<mint>> dp(c+1, vector<mint>(d+1, 0));
  dp.at(a).at(b) = 1;
  rep2(i, a, c+1){
    rep2(j, b, d+1){
      dp.at(i).at(j) += dp.at(i-1).at(j) * j;
      dp.at(i).at(j) += dp.at(i).at(j-1) * i;
      dp.at(i).at(j) -= dp.at(i-1).at(j-1)*(i-1)*(j-1);
    }
  }
  cout << dp.at(c).at(d).x << endl;
  return 0;
}

Measured memory_bytes: 73752
#include <stdio.h>

int main(){
    int n,q;
    scanf("%d",&n);
    long long int s[n+2];
    int w;
    for(w=0;w<=n-1;w++)scanf("%lld",&s[w]);
    scanf("%d",&q);
    
    int i,j;
    int ans=0;
    for(i=0;i<=q-1;i++){
        long long int sta;
        scanf("%lld",&sta);
        s[n]=sta;
        j=0;
        while(sta!=s[j]) j++;
        if(j!=n) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 680
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1e+9;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}




int main() {
  int N,K;
  cin >> N >> K;
  vector<int> v(200100,0);
  rep(i,N) {
    int a;
    cin >> a;
    v[a]++;
  }
  sort(all(v),greater<int>());
  int ans = 0;
  rep(i,K){
    ans += v[i];
  }
  cout << N - ans << endl;
  return 0;
}


Measured memory_bytes: 1656
# https://atcoder.jp/contests/abc151/tasks/abc151_d
# TODO: try
import sys
from collections import deque


def main():
    h, w = map(int, sys.stdin.readline().split())
    area = [[s for s in sys.stdin.readline().strip()] for _ in range(h)]
    start_point = {0: set(), 1: set(), 2: set(), 3: set(), 4: set()}
    min_neighbor = 4
    for i in range(h):
        for j in range(w):
            if area[i][j] == "#":
                continue
            roads = 0
            # 上
            if i > 0 and area[i - 1][j] == ".":
                roads += 1
            # 下
            if i < h - 1 and area[i + 1][j] == ".":
                roads += 1
            # 左
            if j > 0 and area[i][j - 1] == ".":
                roads += 1
            # 右
            if j < w - 1 and area[i][j + 1] == ".":
                roads += 1
            min_neighbor = min(min_neighbor, roads)
            start_point[roads].add((i, j))
    max_cost = 0
    for start in start_point[min_neighbor]:
        # 始点候補からもっとも遠い地点をそれぞれ求める
        queue = deque()
        queue.append(start)
        cost = 0
        visited = set()
        while len(queue) > 0:
            roads = len(queue)
            found = False
            for i in range(roads):
                s = queue.popleft()
                if s in visited:
                    continue
                found = True
                visited.add(s)
                i = s[0]
                j = s[1]
                # 上
                if i > 0 and area[i - 1][j] == ".":
                    queue.append((i - 1, j))
                # 下
                if i < h - 1 and area[i + 1][j] == ".":
                    queue.append((i + 1, j))
                # 左
                if j > 0 and area[i][j - 1] == ".":
                    queue.append((i, j - 1))
                # 右
                if j < w - 1 and area[i][j + 1] == ".":
                    queue.append((i, j + 1))
            if not found:
                cost -= 1
            max_cost = max(cost, max_cost)
            if found:
                cost += 1
    print(max_cost)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9444
#include <array>
#include <cstdlib>
#include <map>
#include <memory>
#include <iostream>
#include <unordered_map>
using namespace std;

constexpr int NUM = 4;
constexpr int MAX_N = 10;

array<int, MAX_N> S;

struct node_t {
	int S_index;
	unique_ptr<node_t> left;
	unique_ptr<node_t> right;

	node_t(int index = -1):S_index(index) {}

	bool is_leaf() const {
		return S_index != -1;
	}

	unordered_map<int, int> calc() const {
		if(is_leaf()) return {{S[S_index], 1}};

		unordered_map<int, int> res;
		const auto l_result = left->calc();
		const auto r_result = right->calc();

		for(const auto &l_e : l_result) {
			for(const auto &r_e : r_result) {
				const int inc = l_e.second * r_e.second;
				res[l_e.first & r_e.first] += inc;
				res[l_e.first | r_e.first] += inc;
				res[l_e.first ^ r_e.first] += inc;
			}
		}
		return res;
	}
};

unique_ptr<node_t> parse(string::const_iterator &it) {
	unique_ptr<node_t> res(new node_t);

	if(isdigit(*it)) {
		res->S_index = *it - '1';
		++it;
	}
	else {
		++it; // '('
		res->left = parse(it);
		++it; // ' '
		res->right = parse(it);
		++it; // ')'
	}
	return res;
}

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

	constexpr int all = (1 << NUM) - 1;

	for(string line; getline(cin, line) && line != "END";) {
		string::const_iterator it = line.cbegin();
		unique_ptr<node_t> root = parse(it);

		int n;
		cin >> n;

		S.fill(0);
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < NUM; ++j) {
				int in;
				cin >> in;
				S[i] |= (in << j);
			}
		}
		cin.ignore();

		auto ans = root->calc();
		cout << ans[all] << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1228
#define _CRT_SECURE_NO_WARNINGS
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <stack>
#include <random>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>

using namespace std;

long long rez, l, r, n;

int main()
{
#if _DEBUG
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
	//freopen("capital.in", "r", stdin);
	//freopen("capital.out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> l >> r;
		if (l > r)
			swap(l, r);
		rez += (r - l + 1);
	}
	cout << rez;
	return 0;
}

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

const int inf = 1000000007;

int main(){ 
    int n,m;
    cin >> n >> m;
    int no[m];
    int stair[n+3] = {0};
    stair[n]=1;
    for(int i=0;i<m;i++){
        cin >> no[i];
        stair[no[i]] = -1;
    }
    for(int i=n-1;i>=0;i--){
        if(stair[i] == -1){
            stair[i] = 0;
            continue;
        }
        else{
            //stair[i] = max(stair[i+1]+stair[i+2],max(stair[i+1],stair[i+2])+0);
            stair[i] = stair[i+1] + stair[i+2];
            stair[i] %= inf;
        }
    }
    cout << stair[0] << endl;

    

    return 0;
}

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }


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

    vector<pair<int,int>> pairs;
    rep(i, n) {
        auto p = make_pair(a[i], i);
        pairs.push_back(p);
    }
    sort(pairs.begin(), pairs.end());

    rep(i, n) {
        cout << pairs[i].second + 1 << endl;
    }

    return 0;
}



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

using namespace std;

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

    int n;

    cin >> n;

    vector<double> dp(n+1);

    //dp[i] = probability of having i heads so far

    dp[0] = 1;

    for(int coin=0; coin<n; coin++){
        double p_heads;
        cin >> p_heads;
        for(int i = coin + 1; i>=0; i--){
            dp[i] = (i == 0 ? 0 : dp[i-1] * p_heads) + dp[i] * (1 - p_heads);
        }
    }

    double ans = 0;

    for(int heads=0; heads<=n; heads++){
        int tails = n - heads;
        if(heads>tails) ans += dp[heads];
    }

    cout.precision(10);
    cout.setf(ios::fixed);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
require 'thread'

class MyProcess
  def initialize(name, quantum)
    @name = name
    @quantum = quantum
  end
  attr_accessor :name, :quantum

  def to_str
    "#{name} #{quantum}"
  end
end

def round_robin_scheduling(queue, quantum)
  time = 0
  array = []
  until queue.empty?
    process = queue.deq
    if process.quantum - quantum <= 0
      time += quantum + process.quantum - quantum
      array << { name: process.name, time: time }
    else
      process.quantum = process.quantum - quantum
      time += quantum
      queue.enq process
    end
  end
  array
end

n, q = gets.split(' ').map(&:to_i)
queue = Queue.new
n.times do
  input = gets.split(' ')
  queue.enq MyProcess.new(input[0], input[1].to_i)
end

result = round_robin_scheduling queue, q
result.each do |hash|
  puts "#{hash.fetch :name} #{hash.fetch :time}"
end



Measured memory_bytes: 22356
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

int N, M, K, Q, W, H, R, C;
int dp[21000][300];

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

    vector<int> ans;
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        vector<int> C(M), x(N);
        REP(i, M) cin >> C.at(i);
        REP(i, N) cin >> x.at(i);

        REP(i, N + 2) {
            REP(j, 300) { dp[i][j] = INF; }
        }
        dp[0][128] = 0;

        REP(i, N) {
            REP(j, 256) {
                REP(k, M) {
                    int v = j + C[k];
                    if (v < 0) {
                        v = 0;
                    } else if (255 < v) {
                        v = 255;
                    }
                    chmin(dp[i + 1][v], dp[i][j] + (x[i] - v) * (x[i] - v));
                }
            }
        }
        int sum = INF;
        REP(i, 256) { chmin(sum, dp[N][i]); }
        ans.push_back(sum);
    }
    for (auto i : ans) {
        cout << i << endl;
    }
    return 0;
}



Measured memory_bytes: 26672
N=int(input())
A=list(map(int,input().split()))
Ad={}
for a in A:
  if a not in Ad:
    Ad[a]=1
  else:
    Ad[a]+=1
sum_A=sum(A)

Q=int(input())
for q in range(Q):
  B,C=map(int,input().split())
  if B in Ad:
    sum_A-=B*Ad[B]
    sum_A+=C*Ad[B]
    if C in Ad:
      Ad[C]+=Ad[B]
    else:
      Ad[C]=Ad[B]
    Ad[B]=0
    pass
  print(sum_A)






Measured memory_bytes: 20620
#include<stdio.h>

int main(void){
    
    int MountHigh[10] = {0};
    int TopHillsThree[3] = {0};
    int ActionNum = 0;
    int MountNum = 0;
    
    //??\?????¨
    fscanf(stdin,"%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d",
           &MountHigh[0],
           &MountHigh[1],
           &MountHigh[2],
           &MountHigh[3],
           &MountHigh[4],
           &MountHigh[5],
           &MountHigh[6],
           &MountHigh[7],
           &MountHigh[8],
           &MountHigh[9]);
    
    //???????????¨???
    for(ActionNum = 1; ActionNum < 10; ActionNum++){
        for(MountNum = 0; MountNum < (10 - ActionNum); MountNum++){
            if(MountHigh[MountNum] < MountHigh[MountNum + 1]){
                const int Temp = MountHigh[MountNum + 1];
                MountHigh[MountNum + 1] = MountHigh[MountNum];
                MountHigh[MountNum] = Temp;
            }
        }
    }
    
    //??£??\??¨???
    TopHillsThree[0] = MountHigh[0];
    TopHillsThree[1] = MountHigh[1];
    TopHillsThree[2] = MountHigh[2];
    
    printf("%d\n%d\n%d\n",
           TopHillsThree[0],
           TopHillsThree[1],
           TopHillsThree[2]);
    
    return(0);
}

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

int f(int a, int b){
    return abs(a-b) * (abs(a-b)-30) * (abs(a-b)-30);
}

int main(){
    int m, w;
    while(cin >> m >> w, m+w){
        int bm[m], bw[w];
        for(int i = 0; i < m; i++)  cin >> bm[i];
        for(int i = 0; i < w; i++)  cin >> bw[i];
        vector<vector<int>> dp(m+1, vector<int>(1<<w, -1));
        dp[0][0] = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < 1<<w; j++){
                if(dp[i][j] < 0)    continue;
                dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
                for(int k = 0; k < w; k++){
                    if((j>>k)&1)  continue;
                    dp[i+1][j|(1<<k)] = max(dp[i+1][j|(1<<k)], dp[i][j]+f(bm[i], bw[k]));
                }
            }
        }
        int ans = 0;
        for(int j = 0; j < 1<<w; j++)   ans = max(ans, dp[m][j]);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3216
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // sankousyo
    int M = sc.nextInt(); // algori
    int X = sc.nextInt(); // 理解度
    int[] yen = new int[N]; // yen
    int[][] ji = new int[N][M]; // 実力
    for(int i=0; i<N ;i++){
      yen[i] = sc.nextInt(); 
      for(int j=0; j<M ;j++){
        ji[i][j] = sc.nextInt(); 
      }
    }
    int min = Integer.MAX_VALUE;
    for(int i = 0 ; i < Math.pow(2,N) ; i++) {
      int[] aa = new int[M];
      int sum = 0;
      for(int j = 0 ; j < N ; j++) {
        if((1 & (i>>j)) == 1) {
          sum += yen[j];
          for(int k =0; k<M ; k++){
            aa[k] += ji[j][k];
          }
        }
        boolean bf = true;
        for(int l =0; l<M ; l++){
          if(aa[l]<X){
            bf = false;
          }
        }
        if(bf==true){min = Math.min(min, sum);}
      }
    }
    if(min==Integer.MAX_VALUE){
      System.out.println(-1); 
    }else{
      System.out.println(min); 
    }
  }

}





Measured memory_bytes: 37732
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define INPUT "/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.in"
#define OUTPUT "/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.out"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define dinf 1e+14

void solve()
{
    int res = 0;
    int n, s;
    cin >> n >> s;
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            res += (s - i - j >= 0 && s - i - j <= n);
        }
    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    //freopen(INPUT, "r", stdin);freopen(OUTPUT, "w", stdout);
    //freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
n = int(input())
p = [0,0]+list(map(int,input().split()))
xls = [0]+list(map(int,input().split()))
dp = [[] for i in range(n+1)]
stack = []
cp = Counter(p)
deg = [cp[i] for i in range(n+1)]
def dp_sol(ls,s):
  l = len(ls)
  mnsm = sum(list(zip(*ls))[0])
  totsm = sum([sum(i) for i in ls])
  if mnsm > s:
    return 10**18
  dp = [[0 for i in range(s+1)] for j in range(l+1)]
  dp[0][0] = 1
  for i in range(1,l+1):
    mn,mx = ls[i-1]
    for j in range(mn,s+1):
      dp[i][j] |= dp[i-1][j-mn]
    for j in range(mx,s+1):
      dp[i][j] |= dp[i-1][j-mx]
  for i in range(s,-1,-1):
    if dp[l][i]:
      return totsm-i
for i in range(1,n+1):
  if cp[i] == 0:
    stack.append(i)
while stack:
  x = stack.pop()
  a = 0
  px = p[x]
  if dp[x]:
    a = dp_sol(dp[x],xls[x])
    if a == 10**18:
      print("IMPOSSIBLE")
      exit()
  if a < xls[x]:
    dp[px].append((a,xls[x]))
  else:
    dp[px].append((xls[x],a))
  deg[px] -= 1
  if deg[px] == 0:
    stack.append(px)
print("POSSIBLE")

Measured memory_bytes: 55004
a,b=map(int,input().split())
c,d=map(int,input().split())
e,f=map(int,input().split())
cnt=[0]*4
cnt[a-1]+=1
cnt[b-1]+=1
cnt[c-1]+=1
cnt[d-1]+=1
cnt[e-1]+=1
cnt[f-1]+=1
if max(cnt)<3:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
constexpr int MAX=100000;
constexpr int NIL=-1;

struct Node{
   int left;
   int right;
   int parent;
};

Node node[MAX];
int dep[MAX];

int setdepth(int u, int d){
   dep[u]=d;
   if(node[u].left!=NIL)
      setdepth(node[u].left, d+1);
   if(node[u].right!=NIL)
      setdepth(node[u].right, d);
}

int main(){
   int n, id, k, c, num;
   cin >> n;
   for(int i=0; i<n; i++) node[i].left=node[i].right=node[i].parent=NIL;
   for(int i=0; i<n; i++){
      cin >> id >> k;
      for(int i=0; i<k; i++){
         cin >> c;
         if(node[id].left==NIL)
            node[id].left=c;
         else 
            node[num].right=c;
         num = c;
         node[c].parent=id;
      }
   }

   int root;
   for(int i=0; i<n; i++){
      if(node[i].parent==NIL) root=i;
   }

   setdepth(root, 0);

   for(int i=0; i<n; i++){
      cout << "node " << i << ": ";
      cout << "parent = " << node[i].parent << ", ";
      cout << "depth = " << dep[i] << ", ";

      if(i==root) cout << "root, ";
      else if(node[i].left==NIL) cout << "leaf, ";
      else cout << "internal node, ";

      cout << "[";
      for(int j=0, c=node[i].left; c!=NIL; j++, c=node[c].right){
         if(j) cout << ", ";
         cout << c;
      }
      cout << "]" << endl;
   }

   return 0;
}


Measured memory_bytes: 4668
#include<stdio.h>

int n , A[50];

//入力値のMから選んだ要素を引いていく再帰関数
int solve (int i, int m){
    if(m == 0)return 1;
    if(i >= n)return 0;
    int res = solve(i+1,m) || solve(i+1,m-A[i]);
    return res;
}

int main(){
    int q,M,i;

    scanf("%d", &n);
    for(i=0; i<n; i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q; i++){
        scanf("%d",&M);
        if(solve(0,M) ) printf("yes\n");
        else printf("no\n");
    }
    return 0;
    

}


Measured memory_bytes: 2092
#include<bits/stdc++.h>
using namespace std;
int h,w,c,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
vector<int> p(64);

int nu(int x,int y,int cl,int t){
  int res=1;
  p[y*w+x]=cl;
  for(int i=0;i<4;i++){
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0||w<=nx||ny<0||h<=ny||p[ny*w+nx]!=t||p[ny*w+nx]==cl)continue;
    res+=nu(nx,ny,cl,t);
  }
  return res;
}

int dfs(int d){
  vector<int> tp=p;
  int res=0;
  if(d==4){
    res=nu(0,0,c,p[0]);
    return nu(0,0,7,p[0]);
  }
  for(int j=1;j<7;j++){
    nu(0,0,j,p[0]);
    res=max(res,dfs(d+1)),p=tp;
  }
  return res;
}

int main(){
  while(cin>>h>>w>>c,h){
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++)cin>>p[i*w+j];
    cout<<dfs(0)<<endl;
  }
  return 0;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e18)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))





int main(){
	
	ll N;
	cin >> N;
	vector<ll> v(N);
	FOR(i,0,N)v[i] = i+1;
	do{
		cout << v[0];
		FOR(i,1,N) cout << ' ' << v[i];
		cout << "\n";
	}while(NEXTP(v));
}



Measured memory_bytes: 3112
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
suma=sum(a)
sumb=sum(b)
if suma<sumb:
  print(-1)
  exit()
d=[]
for i in range(n):
  d.append(a[i]-b[i])
d.sort()
import bisect
minus=bisect.bisect_left(d,0)
sum_minus=sum(d[:minus])
sum_plus=0
ans=minus
i=1
while sum_plus < -sum_minus:
  sum_plus+=d[-i]
  ans+=1
  i+=1
print(ans)


Measured memory_bytes: 18292
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,s,d,f,g,h,i,j;
	scanf("%d",&a);
	while(a!=-1){
		s=4280-1150;
		if(a>10&&a<=20){
			s=4280-((a-10)*125+1150);
		}
		if(a>20&&a<=30){
			s=4280-((a-20)*140+1250+1150);
		}
		if(a>30){
			s=4280-((a-30)*160+1250+1400+1150);
		}
		printf("%d\n",s);
		scanf("%d",&a);
	}
	return 0;
}

Measured memory_bytes: 1028
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void){
    int h[10],i;

    for(i=0;i<10;i++){
	scanf("%d",&h[i]);
    }
    sort(h,h+10);
    printf("%d\n%d\n%d\n",h[9],h[8],h[7]);
    
    return 0;
}

Measured memory_bytes: 2752
#include<bits/stdc++.h>
#define fint register int
#define h 5001
#define p 326498
using namespace std;
int main()
{
	int n;
	cin>>n;
	int ans=0;
	for(fint i=1;i<=n;i++)
	for(fint j=1;j<=n/i;j++)
	{
		if(i*j<n)
		ans++;
	}
	cout<<ans;
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
    int A,B;
    cin >> A >> B;
    int ans;
    if (A >= 13) {
        ans = B;
    }
    else if (A <= 5) {
        ans = 0;
    }
    else {
        ans = B/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int a,b;
	cin >> a >> b;
	if(a <= 9 && b <= 9) cout << a * b << endl;
	else cout << -1 << endl;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;

void main() {
  auto s = readln.splitter;
  auto a = s.front;
  s.popFront();
  auto b = s.front;
  writeln(b, a);
}



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

using namespace std;

int P, N, M, x[100009], vv[100009], ans[100009], p[100009], ap[100009];
long long K;

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
//M = 4, back (1);
//return 0;
for (int i=1; i<=N; i++)
    scanf ("%d", &x[i]), p[i] = i;
for (int i=N; i>=2; i--)
    x[i] -= x[i - 1];
scanf ("%d %lld", &M, &K);
for (int i=1; i<=M; i++)
{
    int j;
    scanf ("%d", &j);
    swap (p[j], p[j + 1]);
}
for (int i=1; i<=N; i++)
if (ap[i] == 0)
{
    int j = i, knt = 0;
    while (ap[j] == 0) ap[j] = 1, j = p[j], vv[knt ++] = j;
    int cat = K % knt;
    for (int p=0; p<knt; p++)
        ans[vv[p]] = vv[(p + cat) % knt];
}
long long curr = x[1];
printf ("%d.0\n", curr);
for (int i=2; i<=N; i++)
{
    curr += x[ans[i]];
    printf ("%lld.0\n", curr);
}

return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
bool a[4];
int main(){
	string s;
	cin>>s;
	for(char c:s){
		if(c=='N') a[0]=1;
		if(c=='S') a[1]=1;
		if(c=='W') a[2]=1;
		if(c=='E') a[3]=1;
	}
	if((a[0]^a[1])||(a[2]^a[3])) puts("No");
	else puts("Yes");
}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a,b; cin >> a >> b;
  ll gcd = __gcd(a,b);
  cout << (a*b)/gcd << endl;
  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 ans = 0;
    string S,T; cin >> S >> T;
    rep(i,3){
        if(S[i] == T[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d", &n, &m), n | m)
	{
		char t[102];	// 1~n
		memset(t, '#', sizeof(t));
		for (int w = 0; w < m; ++w)
		{
			char c;
			scanf(" %c", &c);
			if (c == 'A')
			{
				int i;
				for (i = 1; t[i] != '#'; ++i)
					;
				t[i] = 'A';
			}
			else if (c == 'B')
			{
				int i;
				for (i = n; i >= 1; --i)
					if (t[i-1] != 'A' && t[i] == '#' && t[i+1] != 'A')
						break;
				if (i == 0)
					for (i = 1; t[i] != '#'; ++i)
						;
				t[i] = 'B';
			}
			else if (c == 'C')
			{
				int i;
				if (w == 0)
					i = n / 2 + 1;
				else
				{
					for (i = 1; ; ++i)
						if (t[i] != '#')
							if (t[i+1] == '#')
							{
								++i;
								break;
							}
							else if (t[i-1] == '#' && i > 1)
							{
								--i;
								break;
							}
				}
				t[i] = 'C';
			}
			else
			{
				int i;
				if (w == 0)
					i = 1;
				else
				{
					int dis[102];
					for (int j = 0; j < 102; ++j)
						dis[j] = 100000000;
					for (int j = 1; j <= n; ++j)
					{
						if (t[j] != '#')
							for (int k = 1; k <= n; ++k)
								dis[k] = min(dis[k], abs(j-k));
					}
					int d = 0;
					for (int j = 1; j <= n; ++j)
					{
						if (dis[j] > d)
						{
							i = j;
							d = dis[j];
						}
					}
				}
				t[i] = 'D';
			}
		}
		for (int i = 1; i <= n; ++i)
			putchar(t[i]);
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 0
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int mind = -1;
		for(int i=0; i<=s.length()-t.length(); i++) {
			boolean f = true;
			for(int j=0; j<t.length(); j++) {
				if(s.charAt(i+j) == t.charAt(j) || s.charAt(i+j)=='?') {
					;
				} else {
					f = false;
					break;
				}
			}
			if(f) mind = i;
		}
//		System.out.println(mind);
		String ans = "";
		int j=0;
		for(int i=0; i<s.length(); i++) {
			if(i>=mind && i< mind+t.length()) {
				ans += t.charAt(j);
				j++;
				continue;
			}
			if(s.charAt(i)=='?') {
				ans += 'a';
			} else {
				ans += s.charAt(i);
			}
		}
		if(mind == -1) System.out.println("UNRESTORABLE");
		else System.out.println(ans);
	}
	
	// print
	static void print(String s) {
		System.out.println(s);
	}
	
	// union find lib
	// usage:
	// 最初にinitを呼ぶ
	// root: 直接は呼ばないで
	// unite: まとめる
	// same: グループ判定
	static void init(int par[], int N) {
		for(int i=0; i<N; i++) {
			par[i] = i;
		}
	}
	
	static int root(int x, int [] par) {
		if(par[x] == x) {
			return x;
		} else {
			return (par[x] = root(par[x], par));
		}
	}
	
	static boolean same(int x, int y, int[] par) {
		return root(x, par) == root(y, par);
	}
	
	static void unite(int x, int y, int[] par) {
		x = root(x, par);
		y = root(y, par);
		if(x == y) return;
		par[x] = y;
	}
	
	// end union find lib
	
	// number lib
	
	static int max(int...ls) {
		int ans = Integer.MIN_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.max(ans, ls[i]);
		}
		return ans;
	}
	
	static int min(int...ls) {
		int ans = Integer.MAX_VALUE;
		for(int i=0; i<ls.length; i++) {
			ans = Math.min(ans, ls[i]);
		}
		return ans;
	}
	
	static long lcm(long a, long b) {
		return a*(b/gcd(a, b));
	}
	
	static long gcd(long a, long b) {
		long ta = Math.max(a, b);
		long tb = Math.min(a, b);
		long tmp;
		while((tmp = ta%tb) != 0) {
			ta = tb;
			tb = tmp;
		}
		return tb;
	}
	
	static long modcomb(long n, long k, long mod) {
		if(k==1) {
			return n;
		}
		
		long ans = 1;
		for(long i=n; i>=n-k+1; i--) {
			ans = (ans * i)%mod;
		}
		for(long i=k; 0<i; i--) {
			ans = (ans * modpow(i, mod-2, mod)) % mod;
		}
		return ans;
	}
	
	static long modpow(long a, long b, long mod) {
		if(b==0) return 1;
		if(b%2==0) {
			long d = modpow(a, b/2, mod);
			return (d*d)%mod;
		} else {
			return (a*modpow(a, b-1, mod))%mod;
		}
	}
	
	static int disit(long a, long d) {
		int count = 0;
		while(a!=0) {
			a = a/d;
			count++;
		}
		return count;
	}
	
	// end number lib
}

Measured memory_bytes: 21844
from collections import deque
N,Q = map(int,input().split())
tree = [[] for _ in range(N+1)]
counter = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)
for i in range(Q):
    p,x = map(int,input().split())
    counter[p] += x
already = set()
d = deque([1])

while d:
    a = d.popleft()
    for b in tree[a]:
        if not b in already:
            counter[b] += counter[a]
            d.append(b)
    already.add(a)

print(*counter[1:])

Measured memory_bytes: 159120
def solve(k, a, b):
    for x in range(a, b+1):
        if x % k == 0:
            return "OK"

    return "NG"


if __name__ == '__main__':
    k = int(input())
    a, b = map(int, input().split())
    res = solve(k, a, b)
    print(res)


Measured memory_bytes: 9172
#include<iostream>
#include<iomanip>
#include<complex>
#include<vector>
#include<algorithm>
#include<cmath>

#define EQ(a,b) (abs((a)-(b)) < EPS)
#define fs first
#define sc second

using namespace std;
typedef long double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef pair<P,D> C;

const double EPS = 1e-9;
const double PI = acos(-1);

D arg(D a,D b,D c){return acos( (b*b+c*c-a*a)/(2*b*c) );}

D area_cir(C c){return PI * c.sc * c.sc;}

D intersection_area(C a, C b){
  D d = abs(a.fs-b.fs);
  D ar = a.sc, br = b.sc;
  if(a.sc + b.sc < d + EPS)return 0;
  if(a.sc < b.sc)swap(a,b);
  if(b.sc + d  < a.sc + EPS || b.sc < EPS)return area_cir(b);

  D t1 = arg(b.sc,a.sc,d), t2 = arg(a.sc,b.sc,d);
  D tri = ( a.sc*a.sc*sin(t1*2) + b.sc*b.sc*sin(t2*2) )/2.0;
  return a.sc*a.sc*t1 + b.sc*b.sc*t2 - tri;
}

int main(){
  D Uh,Uw,a,b,ab;
 
  while(cin >> Uw >> Uh >> a >> b >> ab, Uh!=0){
    D rA = sqrt(a/PI), rB = sqrt(b/PI);

    D minlen = min(Uh,Uw);
    if(minlen+EPS<2*rA || minlen+EPS<2*rB){
      cout << "impossible" << endl;
      continue;
    }

    P l = P(rA,rA), r = P(Uw-rB,Uh-rB);
    if(rA < rB){
      l = P(rB,rB); r = P(Uw-rA,Uh-rA);
    }

    C A = C(l,max(rA,rB));
    
    for(int i=0;i<10000;i++){
      P mid = l+r; mid/=2;
      if(intersection_area(A,C(mid,min(rA,rB))) < ab)r = mid;
      else l = mid;
    }

    if(!EQ(intersection_area(A,C(l,min(rA,rB))),ab)){
      cout << "impossible" << endl;
      continue;
    }

    D xA = rA, yA = rA, xB = rB, yB = rB;
    if(rA<rB){
      xA = l.real(); yA = l.imag();
    }else{
      xB = l.real(); yB = l.imag();
    }

    cout << fixed << setprecision(9) << xA << " " << yA << " " << rA << " "
	 << xB << " " << yB << " " << rB << endl;
  }
}

Measured memory_bytes: 1312
#include<bits/stdc++.h>
using namespace std;
long long N;
int main(){
  cin >> N;
  int i=1,ans=0;
  while(1){
    if(ans>N) break;
    ans=i*i;
    i++;
  }
  cout << (i-2)*(i-2) << endl;
  return 0;
}


Measured memory_bytes: 256