akhauriyash/Code-Regression huggingface dataset:
/*
   AUTHOR :- Gaurang_Kothiya
   
   Quote:-" Great things never come from comfort zones."                                                                                                                
*/
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#include <bitset>
#include <cstdint>
#include <initializer_list>
 
using namespace std;
using namespace __gnu_pbds;  

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> data_set; 
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long  
#define ld long double
#define f(i,x,n) for(ll i=x;i<=n;i++)
#define fe(x,v)   for(auto &x :v)
#define nf(i,x,n) for(ll i=n;i>=x;i--)
#define all(a)   a.begin(),a.end()
#define b_s(a,b)   binary_search( all(a),b)
#define lb(v,n)  lower_bound(all(v) ,n )
#define ub(v,n)  upper_bound( all(v) , n)
#define gcd(a,b) __gcd(a,b)
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define RE rend()
#define RB rbegin()
#define B begin()
#define E end()
#define acc(v, x) accumulate(all(v), x)
#define p(a,b) pair<a,b>
#define F first
#define S second
#define sz size()
#define v(x) vector<x>
#define m(a,b) map<a,b>
#define u_m(a,b) unordered_map<a,b>
#define mm(a,b) multimap<a,b>
#define s(a) set<a>
#define us(a) unordered_set<a>
#define ms(a) multiset<a>
#define maxy __LONG_LONG_MAX__
#define miny INT_MIN
#define PI 3.14159265358979323846
#define MOD 1000000007

  


void Solve()
{
	int n,m;
	cin>>n>>m;
	
	int sum=0,x;
	f(i,1,m)
	{
		cin>>x;
		sum +=x;
	}
	
	if(sum>n)cout<<-1;
	else if(sum==n)cout<<0;
	else cout<< n-sum;
	
		
}


signed main() 
{
	speed		
		
	ll q=1;	
	//cin>>q;	
	
	while(q--)	
	Solve();	
	
	//cout << "\n\n"<<"Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " seconds.\n";
	return 0;
}

 
 

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

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

template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

ll n, q;
ll rest;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i, j;
    cin >> n >> q;
    rest = (n - 2) * (n - 2);
    set<P> s[2];
    s[0].insert(P(n, n - 2));
    s[1].insert(P(n, n - 2));
    while (q--) {
        int t, x;
        cin >> t >> x;
        t--;
        auto ii = s[t].lower_bound(P(x, 0));
        // cout << (*ii).fi << " " << (*ii).se << endl;
        if ((s[t].lower_bound(P(x, 0))) == s[t].begin()) {
            s[t].insert(P(x, (*s[1 - t].begin()).fi - 2));
            rest -= (*s[1 - t].begin()).fi - 2;
        } else {
            auto it = --(s[t].lower_bound(P(x, 0)));
            rest -= (*it).se;
        }
    }
    cout << rest << endl;
}

Measured memory_bytes: 16080
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    vector<vi> BA(N);
    rep(i, 0, N) {
        int A, B;
        cin >> A >> B;
        BA[i] = {B, A};
    }
    sort(all(BA));
    int t = 0;
    bool ok = true;
    rep(i, 0, N) {
        t += BA[i][1];
        if (t > BA[i][0]) {
            ok = false;
            break;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
    return (0^_^0);
}



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

int main()
{
    string s;
    cin >> s;
    
    int count = 0;
    
    for(int i = 0; i < s.size(); ++i)
    {
        if(s[i] == '1')
        {
            count++;
        }
    }
    
    cout << count << 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;
typedef pair<ll,ll> P;

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n, a, b;
int ans;

int main(){
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        int j = i;
        int cnt = 0;
        while (j) {
            cnt += j%10;
            j /= 10;
        }
        if (a <= cnt && cnt <= b) ans += i;
    }
    cout << ans << endl;
}
































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

Measured memory_bytes: 1664
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
using namespace std;
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long
#define MOD (int)(1e9+7)

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



int main() {

	ll n, a[100000], ans = 1;

	cin >> n;
	rep(i, 0, n)cin >> a[i];
	sort(a, a + n);
	rep(i, 1, n) {
		if (a[i] == a[i - 1]) {
			ans--;
			a[i]--;
		}
		else ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
import scala.io.StdIn.{readInt, readLine}
object Main {
    def main(args: Array[String]): Unit = {
        val len = readInt
        val arr = new Array[Card](len).map { a => 
            val line = readLine.split(" ")
            Card(line(0), line(1).toInt)
        }
        val arr2 = new Array[Card](len)
        arr.copyToArray(arr2)
        quickSort(arr)
        mergeSort(arr2)
        val q = arr.mkString("\n")
        val m = arr2.mkString("\n")
        if (q == m) println("Stable") else println("Not stable")
        println(q)
    }
    def quickSort(arr: Array[Card]): Unit = {
        def go(left: Int, right: Int): Unit = {
            if (left < right) {
                val (pivot, oneKind) = partition(arr, left, right)
                if (!oneKind) {
                    go(left, pivot - 1)
                    go(pivot + 1, right)
                }
            }
        }
        go(0, arr.length - 1)
    }
    def partition(arr: Array[Card], left: Int, right: Int): (Int, Boolean) = {
        val pivot = arr(right)
        def go(sep: Int, seek: Int, oneKind: Boolean): (Int, Boolean) = seek match {
            case s if s <= right => arr(seek) match {
                case e if e > pivot => go(sep, seek + 1, false)
                case e if e < pivot => {
                    swap(arr, sep + 1, seek)
                    go(sep + 1, seek + 1, false)
                }
                case e => {
                    swap(arr, sep + 1, seek)
                    go(sep + 1, seek + 1, oneKind)
                }
            }
            case s => (sep, oneKind)
        }
        go(left - 1, left, true)
    }
    def mergeSort(arr: Array[Card]): Unit = {
        def go(left: Int, right: Int): Unit = {
            if (left < right) {
                val mid = (left + right) / 2
                go(left, mid)
                go(mid + 1, right)
                merge(left, mid, right)
            }
        }
        def merge(left: Int, mid: Int, right: Int): Unit = {
            val tmp = arr.slice(left, mid + 1)
            var leftPtr = 0
            var rightPtr = mid + 1
            for (i <- (left to right)) {
                if (leftPtr >= tmp.length) {
                    rightPtr += 1
                } else if (rightPtr > right || tmp(leftPtr) <= arr(rightPtr)) {
                    arr(i) = tmp(leftPtr)
                    leftPtr += 1
                } else {
                    arr(i) = arr(rightPtr)
                    rightPtr += 1
                }
            }
        }
        go(0, arr.length - 1)
    } 

    def swap(arr: Array[Card], a: Int, b: Int): Unit = {
        val tmp = arr(a)
        arr(a) = arr(b)
        arr(b) = tmp
    }
}
case class Card(symbol: String, num: Int) {
    override def toString(): String = symbol + " " + num
    def <(a: Card): Boolean = this.num < a.num
    def <=(a: Card): Boolean = this.num <= a.num
    def >(a: Card): Boolean =  this.num > a.num
    def >=(a: Card): Boolean =  this.num >= a.num
}


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

int main() {
    int N;
    std::cin >> N;
    std::vector<int> a(N);
    for (auto& e : a) std::cin >> e;

    int M;
    std::cin >> M;
    std::vector<int> b(M);
    for (auto& e : b) std::cin >> e;

    std::vector<int> ans;
    std::set_difference(a.begin(), a.end(),
                        b.begin(), b.end(),
                        std::back_inserter(ans));

    for (auto& e : ans) std::cout << e << std::endl;
    return 0;
}


Measured memory_bytes: 5448
#include <stdio.h>
int main()
{
	int h,a;
	scanf("%d%d",&h,&a);
	int sum=0;
	while(a--){
		int n;
		scanf("%d",&n);
		sum+=n;
	}
	if(h-sum>0) printf("No");
	else printf("Yes");
	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int ans = 0;
    int n = sc.nextInt();
    int[] l = new int[n];
    for (int cnt = 0; cnt < n; cnt++) {
      l[cnt] = sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          if (i > j && j > k) {
            if (l[i] != l[j] && l[j] != l[k] && l[k] != l[i]) {
              if (l[i] < (l[j] + l[k]) && l[j] < (l[i] + l[k]) && l[k] < (l[i] + l[j])) {
                ans++;
              }
            }
          }
        }
      }
    }
    System.out.println(ans);
    sc.close();
  }
}


Measured memory_bytes: 35948
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tx = br.readLine().split(" ");
        int t = Integer.parseInt(tx[0]);
        int x = Integer.parseInt(tx[1]);
        System.out.println(problem117a(t, x));
    }

    private static String problem117a(int t, int x) {
        return String.format("%.10f", ((t * 1d) / x));
    }
}

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

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    int idx;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] == 1) idx = i;
    }

    cout <<  (N-1+K-1-1) / (K-1) << endl;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrepa(i,a,n) for(int i=(n)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

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

    if(n%2==0)cout<<0.5<<endl;
    else cout<<(((double)n+1)/2)/n<<endl;
    
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

class P
{
    static void Main()
    {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Console.WriteLine(s[2] - s[1] > s[0] ? "dangerous" : (s[2] > s[1] ? "safe" : "delicious"));
    }
}

Measured memory_bytes: 13396
/* ***********************************************
Author        :yang12138
Created Time  :2018年08月18日 星期六 20时15分29秒
File Name     :B.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)



int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
	int n;
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i+=2){
		int cnt=0;
		for(int j=1;j<=i;j++) cnt+=(i%j==0);
		if(cnt==8) ans++;
	}

	cout<<ans<<endl;
    return 0;
}


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

//a>b
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a%b);
}

int vectorgcd(vector<int> a){
	int ans = a[0];
	for(int i = 1; i < (int)a.size(); i++)
	{
		ans = gcd(ans, a[i]);
	}
	return ans;
}

int main(){

	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	
	sort(a.begin(), a.end());
	int ans = vectorgcd(a);
	cout << ans << endl;

	return 0;
}

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

using ll = long long;
using P = pair<ll, ll>;

const ll MOD = 1e9+7;
// const ll MOD = 998244353;
const ll INF = 1ll<<60;

#define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()


int main(int argc, char **argv)
{
	ll a, v, b, w;
	cin >> a >> v >> b >> w;
	ll t; cin >> t;

	ll al = a - v*t;
	ll ar = a + v*t;
	ll bl = b - w*t;
	ll br = b + w*t;

	if (al <= bl && br <= ar)
	{
		std::cout << "YES"<< std::endl;
	}
	else
		std::cout << "NO" << std::endl;
}


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

int main() {
  vector<int> a(3);
  for (int i = 0; i < 3; ++i)
    scanf("%d", &a[i]);
  sort(a.begin(), a.end());
  int ans = a[2] - a[1];
  a[0] += ans;
  a[1] += ans;
  int z = (a[2] - a[0] + 1) / 2;
  ans += z;
  a[0] += z * 2;
  if (a[0] != a[1])
    ++ans;
  printf("%d\n", ans);
  return 0;
}

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

// ABCテンプレート

#define rep(i,n) for (int i = 0; i<(n); i++)
#define in(n) cin >> (n)
#define out(ans) cout << (ans) << endl;
#define keta(n) cout << fixed << setprecision((n));
using ll = int64_t;
using v = vector<int>;


int main() {
  int V;
  cin >> V;
  if(V>=30) cout << "Yes";
  else cout << "No";
}

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

int main() {
    int X;
    cin >> X;
    int maxValue = 0;
    for (int i = 1; i <= 1000; i++) {  // O(N^2) -> 1000 * 1000 = 10^6
        for (int j = 2; j <= 1000; j++) {
            if (pow(i, j) <= X) {
                maxValue = max(maxValue, (int)pow(i, j));
            }
        }
    }

    cout << maxValue << endl;

    return 0;
}


Measured memory_bytes: 4188
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
#define PI 3.141592653589793

int main(){
  int N; string S;
  cin >> N >> S; int cnt = 0, tmp=0;
  rep(i, N){
    if(S[i]== '(') cnt++;
    else cnt--; 
    tmp = min(cnt, tmp);
  }
  string ans = "";
  tmp = -tmp;
  if(tmp>0){
    rep(i, tmp){
      ans.push_back('(');
      cnt++;
    }
  }
  rep(i, N){
    ans.push_back(S[i]);
  }
  if(cnt>0){
    rep(i, cnt){
      ans.push_back(')');
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

//二項係数 mod p
#include <vector>
long long modinv(long long n, long long p) {
	long long a = p, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= p;
	if (u < 0) u += p;
	return u;
}

std::vector<long long> factorial;
std::vector<long long> factorial_inv;
void make_table(long long n, long long p) {
	factorial.resize(n, 1);
	factorial_inv.resize(n, 1);
	for (long long i = 2; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i % p;
	}
	factorial_inv[n] = modinv(factorial[n], p);
	for (long long i = n - 1; i >= 2; i--) {
		factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % p;
	}
}

long long combination(long long n, long long r, long long p) {
	r = std::min(r, n - r);
	long long ret = factorial[n] * factorial_inv[r] % p;
	ret *= factorial_inv[n - r];
	ret %= p;
	return ret;
}

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

	long long x, y, p = 1e9 + 7;
	std::cin >> x >> y;
	if ((x + y) % 3) std::cout << 0 << std::endl;
	else {
		long long z = (x + y) / 3;
		if (x < z || y < z) std::cout << 0 << std::endl;
		else {
			make_table(1e6, p);
			std::cout << combination(z, x - z, p) << std::endl;
		}
	}
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
         
        using namespace std;
         
        int main() {
        	int n, y;
        	scanf("%d %d", &n, &y);
        	int c1 = y / 10000;
        	int c2 = y / 5000;
        	for (int i = 0; i <= c1; i++) {
        		for (int j = 0; j <= c2; j++) {
        			int k = n - i - j;
        			if (k < 0)
        				break;
        			int cur = i * 10000 + j * 5000 + k * 1000;
        			if (cur == y) {
        				printf("%d %d %d\n", i, j, k);
        				return 0;
    				}
        		}
        	}
        	printf(" -1 -1 -1\n");
        	return 0;
        }

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define INF 1000000007
#define LINF 1000000000000000007
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> P;


string s[3];

int main(){
	for(int i = 0; i < 3; i++){
		cin >> s[i];
	}
	
	for(int i = 0; i < 3; i++){
		cout << s[i][i];
	}
	cout << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//debug
#define vecprint(v) rep(i,v.size())cout << v[i] << " ";cout << endl;
#define setprint(s) for(auto i=s.begin();i!=s.end();i++)cout << *i << " ";cout << endl;
#define mappairprint(s) for(auto i=s.begin();i!=s.end();i++)cout << i->first << " " << i->second << endl;cout << endl;
//reader
#define r1(a) cin>>(a)
#define r2(a,b) cin>>(a)>>(b)
#define r3(a,b,c) cin>>(a)>>(b)>>(c)
//writer
#define w1(a) cout<<(a)<<" "
#define w2(a,b) cout<<(a)<<" "<<(b)<<" "
#define w3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "
#define wl1(a) cout<<(a)<<endl
#define wl2(a,b) cout<<(a)<<" "<<(b)<<endl
#define wl3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
//variable definition
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
//roop
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define all(c) c.begin(),c.end()
//term
#define elif else if
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
using namespace std;
using ll = long long;
//const
constexpr double PI = 3.141592653589793238462643383279;
vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};


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

  //process
  n = n % 1000;
  n = 1000 - n;
  if(n >= 1000) n -= 1000;
  
  //output
  cout << n << endl;
}


Measured memory_bytes: 3624
#include<stdio.h>
int main(void){
	int i,j, n,m,c,b[20],a[20][20],sum=0,count=0;
	scanf("%d %d %d", &n, &m, &c);
	for (i = 0; i < m; i++){
		scanf("%d",&b[i]);
	}
	for (i = 0; i < n; i++){
		for (j = 0; j < m; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	for (i = 0; i < n; i++){
		sum = 0;
		for (j = 0; j < m; j++)
		{
			sum = a[i][j] * b[j] + sum;
		}
		sum = sum + c;
		//printf("%d", sum);
		if (sum > 0)
			count++;
	}
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 128
S=input()

if S[0]==S[1] and S[1]!=S[2] and S[2]==S[3]:
    print('Yes')
elif S[0]==S[2] and S[1]!=S[2] and S[1]==S[3]:
    print('Yes')
elif S[0]==S[3] and S[1]!=S[3] and S[1]==S[2]:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
n = gets.to_i
polls = {}
n.times do
  str = gets.chomp
  if polls[str]
    polls[str] += 1
  else
    polls[str] = 1
  end
end

polls = polls.sort {|(k1, v1), (k2, v2)| v2 <=> v1}
biggest = polls[0][1]
ans = []
polls.each do |key, value|
  if value == biggest
    ans << key
  else
    break
  end
end

puts ans.uniq.sort

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

#define inf  1e18
#define int  long long
#define float double
#define endl  "\n"
#define w(t)  int t;cin>>t;while(t--)
#define str  to_string
#define vci  vector<int>
#define vcs  vector<string> 
#define mp   make_pair
#define pb   push_back
#define pii   pair<int,int>
#define pis   pair<int,string>
#define fastio() ios::sync_with_stdio(0);cin.tie(0)
#define mod   1000000007
random_device rd;
mt19937 rand_gen(rd());
#define setbits(x)     __builtin_popcountll(x)
#define trailzero(x)   __builtin_ctzll(x)
#define shuffle(vc) shuffle(vc.begin(), vc.end(), rand_gen);
#define decimal(x,value)  cout<<fixed<<setprecision(x)<<value
void io()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
		freopen("/home/kashif/cp/input.txt","r",stdin);
		
		freopen("/home/kashif/cp/output.txt","w",stdout);
	#endif

}
int n;
vector<int*> v;
int a[100001]={0};
int b[100001]={0};
int c[100001]={0};
int dp[3][100001];

int solve(int curr,int day)
{
	int &ans=dp[curr][day];
	if(ans!=-1)
		return ans;
	ans=0;
	if(day==n)
	{
		
		for(int i=0;i<3;i++)
		{
			if(i!=curr)
				ans=max(ans,v[curr][day]);
		}
		
	}
	else
	{
		
		for(int i=0;i<3;i++)
		{
			if(i!=curr)
				ans=max(ans,v[curr][day]+solve(i,day+1));
		}
			
	}
	return ans;



}



int32_t main()
{
	
	fastio();
	io();
	memset(dp,-1,sizeof(dp));
	v.pb(a);
	v.pb(b);
	v.pb(c);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>v[0][i]>>v[1][i]>>v[2][i];
	}
	int t=solve(0,1);
	int g=solve(1,1);
	int k=solve(2,1);
	cout<<max(max(t,g),k)<<endl;
}


Measured memory_bytes: 16080
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;
//=============segment_tree============================
const int MAX_N = 1 << 17;
int n;
vector<ll> dat(2 * MAX_N - 1, 0);

void init(ll n_) {
  n = 1;
  while (n < n_) {
    n *= 2;
  }
}

void update(ll a, ll b, ll k, ll l, ll r, ll s) {
  if (r <= a || b <= l) {
    return;
  }
  if (a <= l && r <= b) {
    dat.at(k) += s;
  }
  else {
    update(a, b, k * 2 + 1, l, (l + r) / 2, s);
    update(a, b, k * 2 + 2, (l + r) / 2, r, s);
  }
}

ll query(ll k) {
  k += n - 1;
  ll res = dat.at(k);
  while (k > 0) {
    k = (k - 1) / 2;
    res += dat.at(k);
  }
  return res;
}
//=================================================

int main() {
  ll N, Q;
  cin >> N >> Q;
  init(N);
  for (ll i = 0; i < Q; ++i) {
    ll q;
    cin >> q;
    if (q == 0) {
      ll s, t, x;
      cin >> s >> t >> x;
      update(s - 1, t, 0, 0, n, x);
    }
    else {
      ll index;
      cin >> index;
      cout << query(index - 1) << "\n";
    }
  }
}



Measured memory_bytes: 4772
#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define V vector
#define vel V<int>
#define rep(i,n) for(int i=0;i<n;i++)
#define mkp make_pair
#define pin pair<int,int>
pin solve(V<pin>& ab, int ex) {
	if (!ex) { return mkp(0, 0); }
	V<V<pin>> qab(2);
	int sz = ab.size();
	qab[0].reserve(sz);
	qab[1].reserve(sz);
	for (pin& x : ab) {
		qab[x.second & 1].push_back(mkp(x.first / 2, x.second / 2));
		if (x.first & 1) { qab[(x.second + 1) & 1].push_back(mkp(x.first / 2, (x.second + 1) / 2)); }
	}
	int c = 0;
	for (pin& x : qab[0]) {
		int qc = (2 * x.first + x.second) % 3;
		c ^= (qc + 1);
	}
	if (!c) {
		pin ans = solve(qab[1], ex - 1);
		ans.first *= 2; ans.second *= 2; ans.second++;
		return ans;
	}
	pin ans = solve(qab[0], ex - 1);
	c = 0;
	int d = 0;
	for (pin& x : qab[1]) {
		int w = ans.second - x.second - 1;
		if ((w & x.first) == w) { c ^= 1; }
      	w++;
      	if ((w & x.first) == w) { d ^= 1; }
	}
  	ans.first *= 2; ans.second *= 2;
	if (!c&&!d) {
		return ans;
	}
	ans.first+=(c|d); ans.second -= c;
	return ans;
}
signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	long long inf = 1e17;
	int n; cin >> n;
	V<pin> ab(n);
	rep(i, n) {
		long long a, b; cin >> a >> b;
		ab[i] = { a + inf,b + inf };
	}
	pin ret = solve(ab, 59);
	cout << ret.first - inf << " " << ret.second - inf << "\n";
}

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

using namespace std;

void abc_170a();
void abc_171a();
void abc_172a();
void abc_173a();
void abc_174a();
void abc_175a();

void abc_170b();

int main()
{
  //abc_170a();
  //abc_171a();
  //abc_172a();
  //abc_173a();
  //abc_174a();
  //abc_175a();

  abc_170b();

}

void abc_170a()
{
  vector<int> x(5);
  for (int i = 0; i < 5; ++i) cin >> x[i];

  for (int i = 0; i < 5; ++i)
  {
    if (x[i] == 0)
    {
      cout << i + 1 << "\n";
      return;
    }
  }
}

void abc_171a()
{
  char c;
  cin >> c;

  if (c == tolower(c)) cout << "a\n";
  else cout << "A\n";
}

void abc_172a()
{
  int a;
  cin >> a;

  cout << a + a * a + a * a * a << "\n";
}

void abc_173a()
{
  int N;
  cin >> N;

  if (N % 1000) cout << 1000 - N % 1000 << "\n";
  else cout << "0\n";
}

void abc_174a()
{
  int x;
  cin >> x;

  if (x >= 30) cout << "Yes\n";
  else cout << "No\n";
}

void abc_175a()
{
  string s;
  cin >> s;

  int cnt = 0, tmp = 0;
  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i] == 'S')
    {
      tmp = 0;
    }
    else
    {
      ++tmp;
      cnt = tmp;
    }
  }

  cout << cnt << "\n";
}


void abc_170b()
{
  int x, y;
  cin >> x >> y;

  for (int i = 0; i <= x; ++i)
  {
    int n_c = i, n_t = x - i;
    if (n_c * 2 + n_t * 4 == y)
    {
      cout << "Yes\n";
      return;
    }
  }
  cout << "No\n";
}


Measured memory_bytes: 3576
#include <cstdio>
#include <cstring>
typedef long long ll;
int n,s;
ll dp[102][12][1002];

int main(void){
	memset(dp,0,sizeof(dp));
	dp[0][0][0]=1;
	for(int i=0;i<=100;i++){
		for(int j=0;j<=9;j++){
			for(int k=0;k<=1000;k++){
				dp[i+1][j][k]+=dp[i][j][k];
				if(i+k<=1000)dp[i+1][j+1][k+i]+=dp[i][j][k];
			}
		}
	}
	while(1){
		scanf("%d %d",&n,&s);
		if(n==0)break;
		printf("%lld\n",dp[101][n][s]);
	}
	return 0;
}

Measured memory_bytes: 10616
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
//SOLVE


void solve (void)
{
  int N;int M;
  cin>>N>>M;
  vector<int> vec (N,0);
  for (int i = 0; i < N; i++)
  {
     cin>>vec[i];
  }
  vector<int> AccMAX (N,0);
  AccMAX[N-1] = vec[N-1];
  for (int i = N-2; i >= 0; i--) 
  {
    AccMAX[i] = max(AccMAX[i+1],vec[i]);
  }
  int MAX = 0;
  int cnt = 0;
  for (int i = 0; i < N; i++)
  {
    if(chmax(MAX,AccMAX[i] - vec[i]))
    {
      cnt = 1;
    }
    else if(MAX == AccMAX[i] - vec[i])
    {
      cnt++;
    }
  }
  cout<<cnt<<endl;
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 1792
N, x = map(int, raw_input().split())
a = map(int, raw_input().split())
 
ans = 0
 
if a[0] > x:
    ans += (a[0]-x)
    a[0] = x
for i in xrange(len(a)-1):
    if a[i]+a[i+1] > x:
        ans += (a[i]+a[i+1]-x)
        a[i+1] -= (a[i]+a[i+1]-x)
 
print ans

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

int main() {
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i=0; i<N; i++){
      cin >> A.at(i);
  }
  int count = 0;
  while(1){
      N -= K-1;
      count += 1;
      if(N <= 1){
          break;
      }
  }
  cout << count << endl;
}


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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> xy(m);
	for (int i = 0; i < m; i++) {
		cin >> xy[i].first >> xy[i].second;
	}
	sort(xy.begin(), xy.end());
	vector<vector<int>> dp(n, vector<int>(2, 1));
	for (int i = 0; i < n; i++) {
		dp[i][0] = dp[i][1] = i;
	}
	for (int i = 0; i < m; i++) {
		int v = xy[i].second;
		dp[v][0] = dp[v - 1][0];
		dp[v - 1][1] = dp[v][1];
	}
	for (int i = 0; i < n; i++) {
		cout << (dp[i][1] - dp[i][0] + 1) << " \n"[i == n - 1];
	}
	return 0;
}

Measured memory_bytes: 14492
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }

const ll INF=1e18;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    V<ll> imos(n+4,0);
    rep(i,m){
        int l,r;
        cin>>l>>r;
        r++;
        imos[l]++;
        imos[r]--;
    }
    for(int i=1;i<=n;i++) imos[i]+=imos[i-1];
    int ans=0;
    for(int i=1;i<=n;i++)if(imos[i]==m) ans++;
    cout<<ans<<endl;
}
//ペナルティ出しても焦らない　ACできると信じろ！！！
//どうしてもわからないときはサンプルで実験　何か見えてくるかも
//頭で考えてダメなら紙におこせ！！
/*
V,P(大文字)使用不可
乗算などの際にオーバーフローに注意せよ！
(適切にmodをとれ　にぶたんで途中で切り上げろ)
制約をよく読め！
{
    ・全探索できるなら全探索しろ
    ・異常な制約ならそこに注目
}
stringの計算量(扱い)注意
コーナー注意！(特に数値が小さいものについては要検証)
N行出力のときは'¥n'
グリッド上では行先が範囲内におさまるかif文で確認(RE注意)
if文ではちゃんと比較演算子==を使え('='でもエラー出ない)
配列(vector)の大きさが0か1以上かで場合分けせよ(RE注意)
(vector<int> a(m)でm==0というものはできない)
modはなるべく最後に取れ！
doubleを扱うときには(abs)ではなく'fabs'!!!
*/

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
    ll k, n;

    cin >> k >> n;
    vector<int> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    ll max = k + a[0] - a[n - 1], tmp;
    rep(i, n - 1)
    {
        tmp = a[i + 1] - a[i];
        if (max < tmp)
            max = tmp;
    }
    cout << (k - max) << endl;
}

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


int main() {
  string a;
  cin >> a;
  if(a == "A"){
    cout << "T" << endl;
  }else if(a == "T"){
    cout << "A" << endl;
  }else if(a == "C"){
    cout << "G" << endl;
  }else if(a == "G"){
    cout << "C" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

void solve() {
    std::string s, t;
    std::cin >> s;
    std::cin >> t;
    std::cout << t + s << std::endl;
}

int main() {
    // std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]
d = a - b

l = 0
r = 1000000000
while 1 < r - l:
    c = (l + r) // 2
    if c < sum(list(map(lambda hi: max((hi - b * c + d - 1) // d, 0), h))):
        l = c
    else:
        r = c

print(r)

Measured memory_bytes: 120664
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;

// graph template
template<typename T>
class edge{
    public:
        int src, to; T cost;

        edge(int to, T cost): src(-1), to(to), cost(cost){}
        edge(int src, int to, T cost): src(src), to(to), cost(cost){}
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using AdjacencyList = vector<Edges<T>>;
template<typename T>
using Matrix = vector<vector<T>>;

template<typename T>
vector<T> dijkstra(AdjacencyList<T> &g, int s){
    const auto INF = numeric_limits<T>::max();
    vector<T> dist(g.size(), INF);

    using Pr = pair<T, int>;
    priority_queue<Pr, vector<Pr>, greater<Pr>> que;
    dist[s] = 0;
    que.emplace(dist[s], s);

    while(not que.empty()){
        T cost; int v;
        tie(cost, v) = que.top(); que.pop();
        if(dist[v] < cost) continue;

        for(auto &e: g[v]){
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                que.emplace(dist[e.to], e.to);
            }
        }
    }

    return dist;
}

int main(void){
    int V, E, R;
  scanf("%d %d %d", &V, &E, &R);
  AdjacencyList< int > g(V);
  for(int i = 0; i < E; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    g[a].emplace_back(b, c);
  }
  for(auto &dist : dijkstra(g, R)) {
    if(dist == numeric_limits< int >::max()) puts("INF");
    else printf("%d\n", dist);
  }

    return 0;
}


Measured memory_bytes: 15372
#include<stdio.h>
int main()
{
	int w, h, c;
	int k, i, j, large;
	scanf("%d %d %d", &w, &h, &c);

	k = w*h;
	if (w > h)
		large = w;
	else
		large = h;
	
	for (i = large; i > 0; i--) {
		if (w%i == 0 && h%i == 0) {
			printf("%d\n", k / (i*i)*c);
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 2760
N = int(input())

lst = [0] * 5

for i in range(N):
    tgt = input()[0]
    if tgt == 'M':
        lst[0] += 1
    elif tgt == 'A':
        lst[1] += 1
    elif tgt == 'R':
        lst[2] += 1
    elif tgt == 'C':
        lst[3] += 1
    elif tgt == 'H':
        lst[4] += 1

count = 0

for i in range(5):
    for j in range(i + 1, 5):
        for k in range(j + 1, 5):
            count += lst[i] * lst[j] * lst[k]

print(count)

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
from math import sqrt, factorial
from itertools import permutations

N = int(input())
XY = [tuple(map(int, input().split())) for _ in range(N)]

def diff(i, j):
    tmp = (XY[i][0] - XY[j][0]) ** 2 + (XY[i][1] - XY[j][1]) ** 2
    return sqrt(tmp)


ans = 0

for tmp in permutations([i for i in range(N)]):
    score = 0
    for i in range(N - 1):
        score += diff(tmp[i], tmp[i + 1])
    ans += score

print (ans / factorial(N))


Measured memory_bytes: 3188
/*
 Shahadat Hossain
 I.C.T Department
 Comilla University
 Session: 2013-2014
 */

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define valid(x,y) x>=0 && y>=0 && x<n && y<m
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define ms(a,b) memset(a, b, sizeof(a))
#define eps 1e-5
#define input freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)
#define output freopen("/Users/shahadat/Desktop/output.txt", "w", stdout)
#define d(x) cout << #x << " = " << x << endl
#define dd(x,y) cout << #x << " = " << x << "   " << #y << " = " << y << endl
#define ddd(x,y,z) cout << #x << " = " << x << "   " << #y << " = " << y << "   " << #z << " = " << z << endl
//fprintf(stdout,"\nTIME: %.3lf sec\n", (double)clock()/(CLOCKS_PER_SEC));
//int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
#define bit(n,k) (((n)>>(k))&1)
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define pr(x) {cout << (x) << '\n';  }
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define mask(i) ((1LL<<(i)))
#define endl '\n'
double const PI = acos(-1);
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}


int Check(int n, int pos){return n & (1 << pos);}
int Set(int n, int pos){return n |= (1 << pos);}


using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
int const MOD = 1e9 + 7;


int32_t main(){
    int n;
    cin >> n;
    
    vector<double> dp(n + 1);
    
    dp[0] = 1.0;
    for(int item = 1; item <= n; item++){
        double pro;
        cin >> pro;
        double op = 1.0 - pro;
        
        vector<double> new_dp(n + 1);
        for(int i = 0; i < item; i++){
            new_dp[i + 1] += dp[i] * pro;
            new_dp[i] += dp[i] * op;
        }
        dp = new_dp;
    }
    
    double res = 0.0;
    int round = (n / 2) + bool(n % 2);
    for(int i = round; i <= n; i++)
        res += dp[i];
        
    
    cout << fixed << setprecision(9) << res << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<list>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;


int main(){
  long ii,jj,kk;

  unsigned int a,b;

  std::bitset<32> dx;
  
  cin >> a >> b;

  dx = a & b;
  
  cout << dx << endl;

  dx = a | b;
  
  cout << dx << endl;

  dx = a ^ b;

  cout << dx << endl;
  

  
  return 0;
}



Measured memory_bytes: 3164
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int main(){
  int n, k;
  while(scanf("%d%d", &n, &k) && n+k){
    int c[128];
    rep(i, n) scanf("%d", c+i);

    int t = 0;
    int ck = 1;
    rep(i, k) ck *= c[i];
    t = max(t, ck);
    rep(i, n-k){
      ck /= c[i];
      ck *= c[i+k];
      t = max(t, ck);
    }

    int res = 0;
    rep(i, n)  rep(j, n){ //REP(j, i+1, n){
      swap(c[i], c[j]);
      int ck = 1;
      rep(l, k) ck *= c[l];
      res = max(res, ck);
      rep(l, n-k){
	ck /= c[l];
	ck *= c[l+k];
	res = max(res, ck);
	//	printf("%d:%d %d:%d\n", l, c[l], l+k, c[l+k]);
      }
      swap(c[i], c[j]);
    }
    //    printf("%d %d\n", res, t);
    if(res < t) puts("NO GAME");
    else printf("%d\n", res-t);
  }
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define CLR(A, X) memset(A, X, sizeof(A))
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const double eps = 1e-10;
int dcmp(double x) { if(fabs(x) < eps) return 0; return x>0?1:-1; }
const LL MOD = 1e9+7;
const int N = 2e5+5;
const int INF = 0x3f3f3f3f;

int d[2][N][32], a[2][N], pos[N];

void RMQ_init(int n, int v) {
    for(int i = 0; i < n; i++) d[v][i][0] = a[v][i];
    for(int j = 1; (1<<j) <= n; j++)
        for(int i = 0; i+(1<<j)-1 < n; i++)
            d[v][i][j] = min(d[v][i][j-1], d[v][i+(1<<(j-1))][j-1]);
}

int RMQ(int L, int R, int v) {
    int k = 0;
    while((1<<(k+1)) <= R-L+1) k++;
    return min(d[v][L][k], d[v][R-(1<<k)+1][k]);
}

struct node {
    int x, L, R;
    bool operator < (const node& A) const {
        return x > A.x;
    }
};

int main() {
    int n, x;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &x);
        a[i&1][i] = x;
        a[(i&1)^1][i] = INF;
        pos[x] = i;
    }
    RMQ_init(n, 0); RMQ_init(n, 1);
    priority_queue<node> Q;
    x = RMQ(0, n-1, 0);
    Q.push({x, 0, n-1});
    while(!Q.empty()) {
        node x = Q.top(); Q.pop();
        int v1 = x.x, v2 = RMQ(pos[x.x]+1, x.R, (pos[x.x]&1)^1);
        printf("%d %d ", v1, v2);
        v1 = pos[v1], v2 = pos[v2];
        if(x.L != v1) Q.push({RMQ(x.L, v1-1, x.L&1), x.L, v1-1});
        if(v1+1 != v2) Q.push({RMQ(v1+1, v2-1, (v1+1)&1), v1+1, v2-1});
        if(v2 != x.R) Q.push({RMQ(v2+1, x.R, (v2+1)&1), v2+1, x.R});
    }
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1L << 60
#define long long long

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


long N;

int main(){
	cin >> N;
	long min = INF;
	for (long i=1; i<=sqrt(N) ; i++){
		if (N%i == 0){
			long x = N/i;
			chmin(min, i + x-2);
		}
	}
	cout << min << endl;
}

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);

    //入力
    for (int i = 0; i < H; i++) {
        cin >> S.at(i);
    }

    //書き換え
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            
            //爆弾チェック
            if (S.at(i).at(j) == '#') {
                continue;
            }

        
            //爆弾探し
            int count = 0;

            if (i != 0 && j != 0) {
                if(S.at(i-1).at(j-1) == '#') 
                    count++;
            }

            if (i != 0) {
               if(S.at(i-1).at(j) == '#')
                    count++;
           }

            if (i != 0 && j != W-1) {
               if (S.at(i-1).at(j+1) == '#')
                    count++;
            }

            if (j != 0) {
               if (S.at(i).at(j-1) == '#')
                    count++;
            }

            if (j != W-1) {
               if (S.at(i).at(j+1) == '#')
                    count++;
            }

            if (i != H-1 && j != 0) {
               if (S.at(i+1).at(j-1) == '#')
                    count++;
            }

            if (i != H-1) {
               if (S.at(i+1).at(j) == '#')
                    count++;
            }

            if (i != H-1 && j != W-1) {
               if (S.at(i+1).at(j+1) == '#')
                    count++;
            }

           //書き換え
           char c = '0' + count;
           S.at(i).at(j) = c;

        }
    }

    //　出力
    for (int i = 0; i < H; i++) {
        cout << S.at(i) << endl;
    }
    
}

Measured memory_bytes: 256
S = list(input())
frag = 0
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] != "R" and S[i] != "U" and S[i] != "D":
            frag += 1
    if i % 2 == 1:
        if S[i] != "L" and S[i] != "U" and S[i] != "D":
            frag += 1
if frag != 0:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

#define int long long
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// find_by_order(k-1)  returns iterator to kth element starting from 0; Returns the kth smallest element
// order_of_key(k) returns count of elements strictly smaller than k;Returns the number of elements less than k
// erase,insert same as normal set, CAREFUL it does not behave as multiset for it use pii

void solve() {
	int n,w;
	cin>>n>>w;
	vector<int> W(n),V(n);
	for(int i=0;i<n;i++){
		cin>>W[i]>>V[i];
	}

	vector<vector<int>> dp(n,vector<int>(w+1,0));// dp[i][j]-> the max value of items upto weight j and index i that can be taken
	if(W[0]<=w){
		dp[0][W[0]]=V[0];
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<=w;j++){
			dp[i][j]=dp[i-1][j];
			if(j-W[i]>=0)
				dp[i][j]=max(dp[i][j],dp[i-1][j-W[i]]+V[i]);
		}
	}
	int ans=0;
	for(int i=0;i<=w;i++) ans=max(ans,dp[n-1][i]);
	cout<<ans<<endl;
}

int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	// if(fopen("input.txt", "r")){
	//     freopen("input.txt", "r", stdin),
	//     freopen("output.txt", "w", stdout);
	// }
	
	int t = 1;
	//cin>>t;
	for(int i=1;i<=t;i++) {
		//cout<<"Case #"<<i<<": ";
		solve();
	}
}

Measured memory_bytes: 82288
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-10;
const vi emp;

int n;

void dfs(int num,int m,vi ans){
	if(!num){
		for(auto i=ans.begin();i!=ans.end();i++){
			if(i!=ans.begin()) cout<<' ';
			cout<<*i;
		}
		cout<<endl;
		return;
	}
	for(int i=min(num,m);i>0;i--){
		ans.push_back(i);
		dfs(num-i,i,ans);
		ans.pop_back();
	}
}

int main(){
	while(1){
		cin>>n;
		if(!n) return 0;
		vi tmp;
		dfs(n,n,tmp);
	}
}

Measured memory_bytes: 3148