akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define INF 1000000007
#define loop(x) for(int i = 0; i < x; i++)
using namespace std;

long long swapCount = 0;
void swap(vector<int> &arr, int i, int j) {
    if(i == j) {
        return;
    }

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    swapCount++;
}

int f(vector<vector<int>> arr) {
   vector<vector<int>> dp = arr;
   for(int i = 1; i < arr.size(); i++) {
       dp[i][0] = max(arr[i][0] + dp[i - 1][1], arr[i][0] + dp[i - 1][2]);

       dp[i][1] = max(arr[i][1] + dp[i - 1][0], arr[i][1] + dp[i - 1][2]);

       dp[i][2] = max(arr[i][2] + dp[i - 1][1], arr[i][2] + dp[i - 1][0]);
   }
   return max(dp[arr.size() - 1][0], max(dp[arr.size() - 1][2], dp[arr.size() - 1][1]));

}

int main() { 

   //code
   ios::sync_with_stdio(false);
   int t = 1;
    //cin>>t;
    //cin.ignore();
   while(t--) {
        int row, col;
        ////////////////FOR ARRAY
        // cin>>col;
        // vector<int> arr;
        // for(long long i = 0; i < col; i++) {
        //     int x;
        //     cin>>x;
        //     arr.push_back(x);
        // }
        // f(arr);

        //////////////FOR MATIX
        // vector<int> arr;
        // for(int i = 0; i < row; i++) {
        //     arr.push_back(vector<int>(col, 0));
        //     for(int j = 0; j < col; j++) {
        //         int x;
        //         cin>>x;
        //         arr[i].push_back(x);
        //     }
        // }
        // f(arr);

        ////////////FOR STRING
        // string s;
        // cin>>s;
        // cout<<f(s)<<endl;
         int k;
         cin>>col;
        vector<vector<int>> arr;
        for(long long i = 0; i < col; i++) {
            arr.push_back(vector<int>(3, 0));
            int x;
            cin>>x;
            arr[i][0] = x;

            cin>>x;
            arr[i][1] = x;

            cin>>x;
            arr[i][2] = x;
        }
        cout<<f(arr)<<endl;
        
    }
    return 0; 
}

Measured memory_bytes: 17328
//
//  atcoder.cpp
//  
//
//  Created by 中川阿津志 on 2018/12/05.
//
#include <bits/stdc++.h>
#define REP(i, N) for(int i=0; i<N; i++)
using namespace std;

//#include "atcoder.hpp"

long long gcd(long long a, long long b) {
    if (a>b) swap(a,b);
    
    auto r = b % a;
    
    return (r ? gcd(r, a) : a);
}
int main() {
    vector<int> w(1, 1);
    int N;
    string A,B,C;
    cin >> N >> A >> B >> C;


    int r = 0;
    for (int i = 0; i < N; i++) {
        if (A[i]==B[i] && B[i]==C[i])
            continue;
        else if(A[i]==B[i] || B[i]==C[i] || A[i]==C[i])
            r+=1;
        else r+=2;
    }
    cout << r << endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

unsigned int convert10to4( int number );

int main( void )
{
	int number;
	
	while( scanf( "%d", &number ), number != -1 )
	{
		printf( "%u\n", (unsigned)convert10to4( number ) );
	}
	return (0);
}

unsigned int convert10to4( int number )
{
	if( number / 16 == 0 )return ( number / 4 * 10 + number % 4 );
	return ( convert10to4( number / 4 ) * 10 + number % 4 );
}

Measured memory_bytes: 600
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,M=LI()
print("Yes" if N== M else "No")


Measured memory_bytes: 3188
#include<stdio.h>
#define N (100010)
typedef long long LL;
LL a[N],b[N];
int main(){
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",a+i,b+i);
	}
	LL ans=0;
	for (int i=n;i;i--){
		a[i]+=ans;
		LL cur=a[i]/b[i]*b[i];
		if (cur<a[i]) cur+=b[i];
		ans+=cur-a[i];
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 1664
#include <algorithm>
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#define ll long long int
#define eps 1e-7
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define dwn(i, a, b) for(int i = (a); i >= (b); -- i)
using namespace std;

int main()
{
    string s;
    cin >> s;
    int Ans = 0;
    for(int l = 0, r = s.length() - 1; l < r; l ++, r --)
        if(s[l] != s[r])
            Ans ++;
    cout << Ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i;
	char p;
	char ca, cb;
	
	p = 'A';
	while (scanf("%c,%c", &ca, &cb) != EOF){
		if (ca == p){
			p = cb;
		}
		else if (cb == p){
			p = ca;
		}
	}
	printf("%c\n", p);
	
	return (0);
}

Measured memory_bytes: 544
#include <iostream>
#include <stdio.h>
#include<algorithm>
using namespace std;
int main (void)
{
int a;
int b;
int c;
int d=0;
cin>>a>>b>>c;
 if(c>=b&&c>=a){
cout<<a+b<<endl;
}
else if(a>=b&&a>=c)
{
cout<<b+c<<endl;
}

else {
cout<<a+c<<endl;
}}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using str = string;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
const double PI = 3.141592653589793238;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define REP(i, m, n) for (int i = m; i < (int)n; i++)
#define all(a) (a).begin(), (a).end()
#define allg(a) (a).begin(), (a).end(), greator<>()
#define d20 std::setprecision(20)
#define veci vector<int>
#define vecll vector<long long int>
#define vecb vector<bool>
#define vecd vector<double>
template <typename T>
T lcm(T a, T b)
{
	return a / __gcd(a, b) * b;
}

int main()
{
	int a;
	cin >> a;
	cout << a + a* a+a*a*a << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
#define overload4(_1,_2,_3,_4,name,...) name
#define rep1(n) for(ll i=0;i<(n);++i)
#define rep2(i,n) for(ll i=0;i<(n);++i)
#define rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep4(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define vec vector<ll>
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;}
const string YES = "Yes";
const string NO = "No";

void solve(ll n, string s){
    ll r=0;
    rep(i,n)if(s[i]=='R')r++;
    cout<<(r>n-r?YES:NO)<<'\n';
}

int main(){
    ll n;
    scanf("%lld",&n);
    string s;
    cin >> s;
    solve(n, s);
    return 0;
}


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

int main(){
  int64_t N,K;
  cin>>N>>K;
  map<int64_t,int64_t> A;
  for(int64_t i=0;i<N;i++){
    int64_t a,b;
    cin>>a>>b;
    A[a]+=b;
  }
  int64_t j=0;
  for(pair<int64_t,int64_t> i:A){
    j+=i.second;
    if(j>=K){
      cout<<i.first<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 4224
#include <algorithm>
#include <cassert>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

long MOD = 1000000007;

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

    string s1, s2;
    cin >> s1 >> s2;

    vector<long> dp(10);
    dp[9] = 1;

    for (int x = 0; x < N; ) {
        vector<long> ndp(10);

        if (s1[x] == s2[x]) {
            for (int i = 0; i < 10; ++i) {
                int fst = -1;
                int snd = -1;
                if (i < 9) {
                    fst = i % 3;
                    snd = i / 3;
                }

                for (int c = 0; c < 3; ++c) {
                    if (c == fst || c == snd)
                        continue;

                    ndp[c * 3 + c] += dp[i];
                    ndp[c * 3 + c] %= MOD;
                }
            }
            ++x;
        } else {
            for (int i = 0; i < 10; ++i) {
                int fst = -1;
                int snd = -1;
                if (i < 9) {
                    fst = i % 3;
                    snd = i / 3;
                }

                for (int c1 = 0; c1 < 3; ++c1) {
                    if (c1 == fst)
                        continue;

                    for (int c2 = 0; c2 < 3; ++c2) {
                        if (c2 == snd || c1 == c2)
                            continue;

                        ndp[c2 * 3 + c1] += dp[i];
                        ndp[c2 * 3 + c1] %= MOD;
                    }
                }
            }
            x += 2;
        }

        dp.swap(ndp);
    }

    long ans = 0;
    for (int i = 0; i < 10; ++i) {
        ans += dp[i];
        ans %= MOD;
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
using namespace std;
#define mod (long)(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
#define long long long
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<long> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } long C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

int main(){
    int N;
    long x;
    cin >> N >> x;
    long a[N];
    cins(a, a + N);
    long cost[N];
    for(int i = 0; i < N; i++){
        cost[i] = a[i];
    }
    long ans = accumulate(cost, cost + N, 0l);
    for(int i = 1; i < N; i++){
        for(int j = 0; j < N; j++){
            cost[j] = min(cost[j], a[(j - i + N) % N]);
        }
        ans = min(ans, accumulate(cost, cost + N, 0l) + i * x);
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#!/usr/bin/env python3

P_NUM = 1000000007


def solv(n, m, a):
    comb = [1] * (n+1)
    for i in a:
        comb[i] = 0

    for i in range(2, n+1):
        if comb[i] != 0:
            comb[i] = (comb[i-1] + comb[i-2]) % P_NUM

    return comb[-1]


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = [int(input()) for _ in range(m)]

    ans = solv(n, m, a)

    print(ans)


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

int main(){
  vector<char> c(2);
  cin>>c.at(0)>>c.at(1);
  if(c.at(0)<c.at(1)) cout<<"<";
  else if(c.at(0)==c.at(1)) cout<<"=";
  else cout<<">";
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文
int main() {
	int x, a, b;
	cin >> x >> a >> b;
	if (abs(x - a) > abs(x - b)) dump("B") else dump("A");
}

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

int main()
{
    int n,k;
    cin >> n >> k;
    bool dp[k+1] = {};
    int a[n] = {};
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<k; i++){
        for(auto l: a){
            if(i+l <= k){
                if(dp[i] == false) dp[i+l] = true; 
            }
        }
    }
    if(dp[k])
        cout << "First" << endl;
    else
        cout << "Second" << endl;
    return 0;
}

Measured memory_bytes: 384
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * 2 for _ in range(41)]
dp[40][0] = 0

for d in range(1, 41):
    if dp[d-1][1] == 1:
        dp[d][1] = 1

    mask = 1 << (40 - d)
    num_1 = 0
    for i in range(N):
        if A[i] & mask:
            num_1 += 1

    if num_1 >= N - num_1:      # i行目は0にする
        dp[d][0] = dp[d-1][0] + num_1 * (2 ** (40-d))
        if K & mask:
            dp[d][1] = 1
    else:                       # i行目は1にする
        if dp[d][1]:
            dp[d][0] = dp[d-1][0] + (N - num_1) * (2 ** (40 - d))
        else:
            if K & mask:
                dp[d][0] = dp[d-1][0] + (N - num_1) * (2 ** (40 - d))
            else:
                dp[d][0] = dp[d-1][0] + num_1 * (2 ** (40 - d))

print(dp[-1][0])

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

#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() {
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i, n) cin >> d[i];

  ll result = 0;
  rep(i, n) {
    rep(j, n) {
      if (i != j) {
        result += d[i] * d[j];
      }
    }
  }
  cout << result / 2 << endl;

  return 0;
}


Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;
void y(bool c) { if (c)print("Yes"); else print("No"); };

int A, B, C, D, E, X, Y, Z, N, M;
string S, T;
void solve() {
	string S; cin >> S;
	y(S[0] == '7' || S[1] == '7' || S[2] == '7');
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}




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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    int t = n - 1; 
    sort(a.rbegin(), a.rend());
    ll ans = 0;
    rep(i, n) {
        int lim = 2;
        if (i == 0) lim = 1;
        rep(j, lim) {
            if (t > 0) {
                ans += a[i];
                t--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4004
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;
using static System.Console;
//using System.Numerics;
//using static System.Math;
using pair = Pair<int, int>;

class Program
{
    static void Main()
    {
        //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        new Program().solve();
        Out.Flush();
    }
    Scanner cin = new Scanner();
    readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
    readonly int mod = 1000000007;


    void solve()
    {
        int N = cin.nextint;
        var U = new pair[N];
        for (int i = 0; i < N; i++)
        {
            U[i] = new pair(cin.nextint, cin.nextint);
        }
        U = U.OrderBy(i => i.f + i.s).ThenBy(i => i.s).ToArray();

        var dp = new long[N + 1]; // i人置いたときの最小の高さ
        for (int i = 0; i < N + 1; i++)
        {
            dp[i] = long.MaxValue;
        }
        dp[0] = 0;
        

        for (int i = 0; i < N; i++)
        {
            for (int j = i; j >= 0; j--)
            {
                if (dp[j] <= U[i].f)
                {
                    dp[j + 1] = Math.Min(dp[j + 1], dp[j] + U[i].s);
                 }
            }
            //WriteLine(string.Join(" ", dp));
        }
        
        for (int i = N; i >= 0; i--)
        {
            if (dp[i] != long.MaxValue)
            {
                WriteLine(i);
                return;
            }
        }
    }

}

class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
    public T f;
    public U s;
    public Pair(T f, U s)
    {
        this.f = f;
        this.s = s;
    }
    public int CompareTo(Pair<T, U> a)
    {
        return f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);
    }
    public override string ToString()
    {
        return f + " " + s;
    }
}
class Scanner
{
    string[] s; int i;
    char[] cs = new char[] { ' ' };
    public Scanner() { s = new string[0]; i = 0; }
    public string[] scan { get { return ReadLine().Split(); } }
    public int[] scanint { get { return Array.ConvertAll(scan, int.Parse); } }
    public long[] scanlong { get { return Array.ConvertAll(scan, long.Parse); } }
    public double[] scandouble { get { return Array.ConvertAll(scan, double.Parse); } }
    public string next
    {
        get
        {
            if (i < s.Length) return s[i++];
            string st = ReadLine();
            while (st == "") st = ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            i = 0;
            return next;
        }
    }
    public int nextint { get { return int.Parse(next); } }
    public long nextlong { get { return long.Parse(next); } }
    public double nextdouble { get { return double.Parse(next); } }
}

Measured memory_bytes: 13664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr long long INF = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;



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

    int N;
    cin>>N;
    N--;
    string ans="";
    while(N>=0){
        int x=N%26;
        N/=26;
        N--;
        char y='a';
        y=y+x;
        ans=ans+y;
    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;

    



}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d,e,f,g,h,i;
  cin>>a>>b>>c>>d>>e>>f>>g>>h>>i;
  if(d-a==e-b&&e-b==f-c&&d-g==e-h&&e-h==f-i)cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: u32) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::cmp::min;

fn main() {
    let v: Vec<u64> = read_vec();
    let l = v[0];
    let r = v[1];

    if r - l > 700 {
        println!("0");
    } else {
        let mut ans: u64 = 10000;
        for i in l..r {
            for j in (i + 1)..(r + 1) {
                ans = min(ans, (i * j) % 2019);
            }
        }
        println!("{}", ans);
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp> // Including seg_tree_order_statistics_node_update
#include <stdio.h>
#include <cassert>
using namespace std;
//using namespace __gnu_pbds;
typedef long long lo;
typedef pair<lo,lo> ll;//pair
typedef vector<lo> vl;  //vector of long
typedef vector<ll > vll;   //vector of pair
typedef priority_queue<lo>p_q;
typedef vector< vl > vvl;  //vector of vectors
#define X first
#define Y second
#define mp(a,b) make_pair((a),(b))
#define REP(a,b) for(lo i=(a);i<(lo)b;i++)//no need to declare variable i
#define REPE(a,b,c,d) REP(a,b)for(lo j=(c);j<(lo)d;j++)//no need to declare vaiables i,j
#define REPV(a,b,c) for((a)=b;(a)<(c);(a)++)//a is the variable
#define IREP(a,b) for(lo i=(a);i>=(b);i--)
#define IREPV(a,b,c) for((a)=b;(a)>=(c);(a)--)
#define all(v) (v).begin(),(v).end()
#define TRV(a) for(auto it : a)
#define INF 200100
#define MOD 1000000007
#define M 1000000007
#define CHECK_BIT(var,pos) ((var) & (1<<(pos)))
#define pb(a) push_back((a))
/*order statistic tree
typedef
tree<
  lo,
    null_type,
  less_equal<lo>,
  rb_tree_tag,
  // This policy updates nodes' metadata for order statistics.
  tree_order_statistics_node_update>
ordered_set;*/

/*#define gc getchar_unlocked
#define pc putchar_unlocked
inline void sprlo( lo a){
    lo i=0;
    char S[20];
    if(a==0)pc('0');
    if(a<0){
        pc('-');
        a*=-1;
    }
    while(a>0){
        S[i++]=a%10+'0';
        a=a/10;
    }
    --i;
    while(i>=0)
    pc(S[i--]);
    pc(' ');
}
inline void lprlo( lo a){
    lo i=0;
    char S[20];
    if(a==0)pc('0');
    while(a>0){
        S[i++]=a%10+'0';
        a=a/10;
    }
    --i;
    while(i>=0)
    pc(S[i--]);
    pc('\n');
}
inline lo uscan(){
    lo n=0;
    char c=gc();
    while(c<'0'||c>'9')c=gc();
    while(c<='9'&&c>='0'){
	    n=n*10+c-'0';
	    c=gc();
	}
    return n;
}*/
template<typename T> ostream& operator<< ( ostream &o,vector<T> v ) {
    if ( v.size() >0 )o<<v[0];
    for ( unsigned   i=1; i<v.size(); i++ )o<<" "<<v[i];
    return o<<endl;
}
template<typename U,typename V> ostream& operator<< ( ostream &o,pair<U,V> p ) {
    return o<<"("<<p.first<<", "<<p.second<<") ";
}
template<typename T> istream& operator>> ( istream &in,vector<T> &v ) {
    for ( unsigned   i=0; i<v.size(); i++ )in>>v[i];
    return in;
}
template<typename T> istream& operator>> ( istream &in,pair <T,T> &p ) {
    in>>p.X;
    in>>p.Y;
    return in;
}
bool dig(lo n){
    lo x=0;
    while(n>0){
        if(n%10==9)return true;
        n/=10;
        x++;
    }
    return false;;
}
int main(){
    std::ios::sync_with_stdio(false);
	lo n;
	cin>>n;
	if(dig(n))cout<<"Yes";
	else cout<<"No";
	return 0;
}


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

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

	vector<int> SX(n), SY(n), CX(m), CY(m);

	for(int s=0; s<n; s++) cin>>SX[s]>>SY[s];
	for(int c=0; c<m; c++) cin>>CX[c]>>CY[c];

	for(int s=0; s<n; s++){
		int mini = 1e9, ans = 0;
		for(int c=0; c<m; c++){
			int m  = abs(SX[s]-CX[c]) + abs(SY[s]-CY[c]);
			if(mini>m){ mini = m; ans = c+1; }
		}
		cout<< ans <<endl;
	}
}

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

MOD = 998244353

L_list = []
R_list = []
for i in range(K):
    L, R = map(int, input().split())
    L_list.append(L)
    R_list.append(R)

dp = [0] * (N+1)
dp[0] = 0
dp[1] = 1
sdp = [0] * (N+1)
sdp[0] = 0
sdp[1] = 1


for i in range(2, N+1):
    for j in range(len(L_list)):
        if i - R_list[j]-1 < 0:
            R_pos = 0
        else:
            R_pos = i - R_list[j] - 1
        dp[i] += (sdp[i - L_list[j]] - sdp[R_pos])%MOD
        dp[i] %= MOD
    sdp[i] = sdp[i-1] + dp[i]
    sdp[i] %= MOD
    #print(dp)
    #print("s", sdp)
print(dp[N])

Measured memory_bytes: 24500
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>

typedef long long ll;

using namespace std;

int main()
{
    ll n, a, b, ans;
    cin >> n >> a >> b;

    ans = (n * a < b) ? n*a : b;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
using namespace std;
using ll =long long;
const int MOD = 1000000007;

//////検証する数,超えられない数////
long long cine(long long a, long long b) {
	if (a <= b) {
		return a;
	}
	else {
		return b;
	}
};
//vector型の初期化
void vec_initialize(vector<ll>& a, const ll N) {
	ll c;

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

		cin >> c;
		a.push_back(c);

	}

};
void vec_pair_initialize(vector<pair<ll, ll>>& a, const ll N) {
	ll c, d;
	for (int i = 0; i < N; i++) {
		cin >> c >> d;
		a.push_back(make_pair(c, d));
	}
};
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main() {

	int N;
	cin >> N;
	vector<int>t, x, y;
	t.resize(N+1);
	x.resize(N+1);
	y.resize(N+1);
	x[0] = 0;
	y[0] = 0;
	t[0] = 0;
	int p, q,T;
	for (int i = 1; i <= N; i++) {
		cin >> t[i] >> x[i] >> y[i];
	}
	for (int i = 1; i <= N; i++) {
		p = abs(x[i] - x[i - 1]);
		q = abs(y[i] - y[i - 1]);
		T = t[i] - t[i - 1];
		if (T<p +q||(T-p - q)%2!=0){   

			cout << "No";
			return 0;
		}

	}
	cout << "Yes";
}

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n; cin>>n;
  vi v(9,0);
  rep(i,n){
    int a; cin>>a;
    if(a<400)v[0]=1;
    else if(a<800)v[1]=1;
    else if(a<1200)v[2]=1;
    else if(a<1600)v[3]=1;
    else if(a<2000)v[4]=1;
    else if(a<2400)v[5]=1;
    else if(a<2800)v[6]=1;
    else if(a<3200)v[7]=1;
    else v[8]++;
  }
  int mi=0;
  rep(i,8){
    if(v[i])mi++;
  }
  
  int ma=mi+v[8];
  if(mi==0)mi=1;
  
  cout<<mi<<" "<<ma<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 2147483647
//static const double INF = (1 << 31)-1;

int n,q;
double d[400000],lazy[400000];
double x;

void lazy_evaluate(int k,int l,int r){
	if(lazy[k] == INF)return;
	else{
		d[k] = lazy[k];
		if(r - l > 1){
			lazy[2*k+1] = lazy[k];
			lazy[2*k+2] = lazy[k];
			/*
			lazy_evaluate(2*k+1);
			lazy_evaluate(2*k+2);
			*/
		}
		lazy[k] = INF;
	}
}
/*
void update(int k,double a){
	k += n - 1;
	d[k] = a;
	while(k > 0){
		k = (k - 1)/2;
		d[k] = min(d[k*2+1], d[k*2+2]);
	}
}
*/
void query(int a, int b, int k=0, int l=0, int r=-1){
	if(r < 0){
		r = n;
	}
	//cout << "haittemasu" << endl;
	
	lazy_evaluate(k,l,r);
	if(b <= l || r <= a) return;
	else if(a <= l && r <= b){
		lazy[k] = x;
		lazy_evaluate(k,l,r);
	}
	else{
		query(a,b,2*k+1,l,(l+r)/2);
		query(a,b,2*k+2,(l+r)/2,r);
		d[k] = min(d[2*k+1], d[2*k+2]);
	}
}

/*
double query(int a, int b, int k, int l, int r){
	if(r <= a || b <= l){
		return INF;
	}
	else if(a <= l && r <= b){
		return d[k];
	}

	double vl = query(a, b, k*2+1, l, (l + r)/2);
	double vr = query(a, b, k*2+2, (l + r)/2, r);
	return min(vl, vr);
}

double findMin(int a, int b){
	return query(a, b+1, 0, 0, n);
}
*/

void find(int a, int b, int k=0, int l=0, int r=-1){
	if(r < 0){
		r = n;
	}
	lazy_evaluate(k,l,r);
	if(b <= l || r <= a){
		return;
	}
	else if(a <= l && r <= b){
		return;
	}

	//double vl = 
	find(a, b, k*2+1, l, (l + r)/2);
	//double vr = 
	find(a, b, k*2+2, (l + r)/2, r);
	//return min(vl, vr);

}

int main(){
	int n_;
	cin >> n_ >> q;

	n=1;
	while(n<n_){
		n*=2;
	}
	for(int i = 0;i < n*2-1;i++){
		d[i] = INF;
		lazy[i] = INF;
	}
	int a, b;   
	double s,t;
	for(int i = 0;i < q;i++){
		cin >> a;
		if(a == 0){
			cin >> s >> t >> x;
			query(s,t+1);
		}
		else{
			cin >> b;
			find(b,b+1);
			printf("%.0f\n",d[b+n-1]);
		}
	}
	/*
	for(int i = 0;i < n*2-1;i++){
		cout << d[i] << endl;
	}
	*/
	return 0;
}



Measured memory_bytes: 7304
my $s = <STDIN>;
my @dat = split(/ /,$s);
my $N = $dat[0];
my $K = $dat[1];
my $Q = $dat[2];
chomp $Q;
#print "$N $K $Q\n";
my @point;
for($j=1;$j<=$N;$j++){
  $point[$j] = $K -$Q;
}

for($i=0;$i <$Q;$i++){
  $s = <STDIN>;
  chomp $s;
  $s = $s + 0;
  #print "$s $point[$s] \n";
  $point[$s] =  $point[$s] + 1;
}
for($j=1;$j<=$N;$j++){
  if( $point[$j] <= 0 ){
    #print "$j $point[$j] ";
    print "No\n";
  }else{
    print "Yes\n";
  }
}


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

int main(){
    long long A,B,C;
    cin>>A>>B>>C;

    if(22<=A+B+C)cout<<"bust";
    else cout<<"win";
    return 0;
}

Measured memory_bytes: 3616
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
vector<complex<double>>  DFT(vector<complex<double>> a) {
	int n = a.size();
	if (n == 1) return a;
	vector<complex<double>> a0(n / 2), a1(n / 2);
	REP(i, n) {
		if (i % 2 == 0) {
			a0[i / 2] = a[i];
		}
		else {
			a1[i / 2] = a[i];
		}
	}
	vector<complex<double>> inversed_a0 = DFT(a0), inversed_a1 = DFT(a1);
	vector<complex<double>> inversed_a(n);
	for (int i = 0; i < n; ++i) {
		complex<double> zeta = complex<double>(cos(2 * Ma_PI * i / n), sin(2 * Ma_PI * i / n));
		inversed_a[i] = inversed_a0[i % (n / 2)] + zeta * inversed_a1[i % (n / 2)];
	}
	return inversed_a;
}
vector<complex<double>> IDFT(vector<complex<double>> inversed_a) {
	int n = inversed_a.size();
	vector<complex<double>> now = DFT(inversed_a);
	reverse(now.begin(), now.end());
	for (int q = now.size() - 1; q >= 1; --q) {
		swap(now[q], now[q - 1]);
	}
	REP(i, n) {
		now[i] /= complex<double>(n, 0);
	}
	return now;
}
vector<complex<double>> conv(vector<complex<double>> a, vector<complex<double>> b) {
	int deg = a.size() + b.size() - 1;
	int n = 1;
	while (n < deg) n <<= 1;
	a.resize(n);
	b.resize(n);
	vector<complex<double>> inversed_a = DFT(a),inversed_b = DFT(b);
	vector<complex<double>> inversed_c(n);
	REP(i, n) {
		inversed_c[i] = inversed_a[i] * inversed_b[i];
	}
	return IDFT(inversed_c);
}

vector<pair<long long, long long>> inputs;
int here[200000];
int main(){
	int n;
	cin >> n;
	long long tmp[2] = {};
	long long ans = 0;
	vector<pair<long long, long long>> next;
	REP(i, n) {
		long long a, b;
		cin >> a >> b;
		inputs.push_back(make_pair(a, b));
		tmp[0] += a;
		tmp[1] += b;
		next.push_back(make_pair(a, i));
		next.push_back(make_pair(b, i));
	}
	ans = min(tmp[0], tmp[1]);
	sort(next.begin(), next.end());
	long long now_ans = 0;
	int ok = 0;
	REP(i, n) {
		here[next[i].second]++;
		if (here[next[i].second] == 2) {
			ok = 1;
		}
		now_ans += next[i].first;
	}
	if (ok == 1) {
		ans = min(ans, now_ans);
	}
	else {
		for (int i = 0; i < n; ++i) {
			long long tmp = -next[i].first;
			if (next[n].second != next[i].second) {
				tmp += next[n].first;
			}
			else {
				tmp += next[n + 1].first;
			}
			ans = min(ans, now_ans + tmp);
		}
	}
	cout << ans << endl;
	return 0;
}

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

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

int N,M;
int lef[1111];
int dp[1111];

signed main(){
    cin>>N>>M;
    N++;
    fill_n(lef,1111,1<<30);
    rep(i,M){
        int c,d;
        cin>>c>>d;
        c--;d--;
        chmin(lef[d],c);
    }

    fill_n(dp,1111,1<<30);
    dp[0]=0;
    reps(i,1,N+1){
        int most_lef=i;
        for(int j=i-1;j>=0;j--){
            chmin(most_lef,lef[j+1]);
            chmin(dp[i],dp[j]+(i-j)+(i-most_lef)*2);
        }
    }

    cout<<dp[N]<<endl;

    return 0;
}

Measured memory_bytes: 3128
n, x, y = map(int, input().split())
ans = [0] * n
x -= 1
y -= 1

for i in range(n):
    for j in range(i+1, n):
        dis = min((j-i), abs(x-i)+1+abs(y-j))
        # print("i:", i, "j:", j, dis)
        ans[dis] += 1

for a in ans[1:]:
    print(a)

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

int main(){
    string s;
    cin >> s;
    int zerostrt = 0;
    int onestrt = 0;

    for(int i = 0;i < s.size();i++){
        if(i % 2 == 0){
            if(s[i] == '0'){
                zerostrt++;
            }else{
                onestrt++;
            }
        }else{
            if(s[i] == '1'){
                zerostrt++;
            }else{
                onestrt++;
            }
        }
    }
    cout << min(zerostrt,onestrt);
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
#define PI acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define nl printf("\n")
#define sf scanf
#define pf printf
#define INF (ll)1e15
#define mod 1000000007

///#define isValid(n,m,nx,ny)nx>=0&&nx<n&&ny>=0&&ny<m
///int kx[]={1, 1, -1, -1, 2, 2, -2, -2}; //knight moves
///int ky[]={2,-2,  2, -2, 1,-1,  1, -1}; //knight moves
///int dx[]={1,-1,0,0,1,-1,1,-1};//eight direction
///int dy[]={0,0,1,-1,1,-1,-1,1};//eight direction
 
///using namespace __gnu_pbds;
using namespace std;
 
///inline double toRad(double deg){return deg*PI/180;}
///inline double toDeg(double rad){return rad*180/PI;}
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;

typedef pair<ll,ll>ii; 
const int S=123456;
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    #endif
    int n,m;
    while(cin>>n>>m)
    {
        vector<int>graph[n+5];
        for(int i=0;i<n;i++)graph[i].clear();

        for(int i=1;i<=m;i++)
        {
            int u,v;
            cin>>u>>v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        queue<int>q;
        while(!q.empty())q.pop();
        q.push(1);

        int level[n+5];
        memset(level,-1,sizeof level);
        level[1]=0;

        bool visit[n+5];
        memset(visit,false,sizeof visit);

        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            visit[u]=true;
            for(auto v:graph[u])
            {
                if(!visit[v])
                {
                    q.push(v);
                    level[v]=level[u]+1;
                    visit[v]=true;
                }
            }
        }
        if(level[n]!=2)puts("IMPOSSIBLE");
        else puts("POSSIBLE");
    }
    return 0;
}
 









 




























Measured memory_bytes: 13424
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


X, Y, Z, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))
C = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int)
B = np.array(B, dtype=int)
C = np.array(C, dtype=int)

AB = (A[:, None] + B[None, :]).ravel()
AB.sort()
AB = AB[::-1]

# K番目の美味しさをにぶたん
l = 0
h = IINF
while abs(l - h) > 1:
    d = (l + h) // 2
    # 美味しさが d 以上になる選び方の数
    cnt = np.searchsorted(d - AB, C, side='right').sum()
    if cnt >= K:
        l = d
    else:
        h = d

# 美味しさが h 以上のやつを集めてソート
counts = list(np.searchsorted(h - AB, C, side='right'))
ans = []
for i, cnt in enumerate(counts):
    ans += (AB + C[i])[:cnt].tolist()
ans += [l] * (K - len(ans))
ans.sort(reverse=True)
if ans:
    print(*ans, sep='\n')


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

#define int long long

signed main(){
    string s;
    cin >> s;
    int m;
    m = s.size();

    s.push_back('Y');

    string t;
    for(int i = 0;i < m;i++){
        if(s[i] == 'B' && s[i+1] == 'C'){
            t.push_back('D');
            i++;
        }else{
            t.push_back(s[i]);
        }
    }

    int ans = 0;
    int d = 0;
    for(int i = t.size()-1;i >= 0;i--){
        if(t[i] == 'D'){
            d++;
        }else if(t[i] == 'A'){
            ans += d;
        }else{
            d = 0;
        }
    }

    cout << ans << endl;

    return 0;
}










Measured memory_bytes: 776
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,m = lr()
xyz = [lr() for i in range(n)]
ans = -inf
for i in range(2**3):
    tmp = [0 for i in range(n)]
    for j in range(3):
        if (i >> j) & 1:
            for k in range(n):
                tmp[k] += xyz[k][j]
        else:
            for k in range(n):
                tmp[k] -= xyz[k][j]
    tmp.sort(reverse=True)
    ans = max(sum(tmp[:m]),ans)
print(ans)


Measured memory_bytes: 79424
n, y = map(int, input().split())
sum = 0

for i in range(n+1):
	for j in range(n-i+1):
		k = n - i - j
		if k >= 0:
			sum = 10000*i + 5000*j + 1000*k
			if sum == y:
				print(i, j, k)
				exit()
print('-1 -1 -1')

Measured memory_bytes: 3060
#include<iostream>

using namespace std;

int main(){
    int a[100];
    int b[100];
    int c[100];
    int n=0;
    int m=0;
    int k=0;
    int l=0;

    for(int i=0;i<100;i++){
        cin >> a[i] >> b [i] >> c[i];

        if(a[i]+b[i]<=c[i] || a[i]+c[i]<b[i] || b[i]+c[i]<a[i]){
            break;
        }else if(a[i]*a[i]+b[i]*b[i]==c[i]*c[i] || a[i]*a[i]+c[i]*c[i]==b[i]*b[i] || b[i]*b[i]+c[i]*c[i]==a[i]*a[i]){
            n++;
            m++;
        }else if(a[i]*a[i]+b[i]*b[i]<c[i]*c[i] || a[i]*a[i]+c[i]*c[i]<b[i]*b[i] || b[i]*b[i]+c[i]*c[i]<a[i]*a[i]){
            n++;
            k++;
        }else{
            n++;
            l++;
        }
    }
    cout << n << " " << m << " " << l << " " << k << endl;
}


Measured memory_bytes: 3088
X = int(input())

X_half = X // 2
max_ans = 1
tmp_max = 0

for i in range(1,X_half+10):
    for j in range(2,X_half+10):
        tmp = i ** j
        if tmp<=X:
            tmp_max = tmp
    max_ans = max(max_ans, tmp_max)

print(max_ans)


Measured memory_bytes: 40428