akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <bitset>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

void solve() {
    int n, m;
    std::cin >> n >> m;

    int csum = 0;
    std::vector<int> cost(1 << n, 0);
    while (m--) {
        int u, v, c;
        std::cin >> u >> v >> c;
        --u, --v;

        for (int b = 0; b < (1 << n); ++b) {
            if (((b >> u) & 1) && ((b >> v) & 1)) {
                cost[b] += c;
            }
        }
        csum += c;
    }

    auto dp = vec(n, vec(1 << n, -1));
    dp[0][0] = 0;
    for (int b = 0; b < (1 << n); ++b) {
        for (int v = 0; v < n; ++v) {
            if (dp[v][b] == -1) continue;

            auto cb = ~b & ((1 << n) - 1);
            for (int c = cb; c > 0; c = (c - 1) & cb) {
                if (!((c >> v) & 1)) continue;

                int nb = b | c;
                int gcost = cost[c];

                for (int u = 0; u < n; ++u) {
                    int pcost = cost[(1 << u) | (1 << v)];
                    if (u == v ||
                        ((nb >> u) & 1) ||
                        pcost == 0) continue;

                    dp[u][nb] = std::max(dp[u][nb],
                                         dp[v][b] + gcost + pcost);
                }
            }
        }
    }

    int ans = 0;
    for (int b = 0; b < (1 << n); ++b) {
        if (dp[n - 1][b] == -1) continue;
        auto cb = ~b & ((1 << n) - 1);
        ans = std::max(ans, dp[n - 1][b] + cost[cb]);
    }

    std::cout << csum - ans << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>

int main(){

    int N, X, T;

    scanf("%d", &N);
    scanf("%d", &X);
    scanf("%d", &T);

    int time=0;

    while(N>0){
        time+=T;
        N=N-X;
    }

    printf("%d\n", time);

    return 0;
}

Measured memory_bytes: 2136
#include <stdio.h>

int main(void)
{
    int k,n;
    scanf("%d %d",&k,&n);
    int a[n+1];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int tmp=a[0];
    for(int i=0;i<n;i++){
        a[i]-=tmp;
    }
    int d=k-a[n-1];
    for(int i=0;i<n-1;i++){
        if(a[i+1]-a[i]>d){
            d=a[i+1]-a[i];
        }
    }
    printf("%d",k-d);
}

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

int main() {
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        A.at(i)--;
    }
    long long cur = 0, cf = 0, cp = 0;
    vector<bool> a(N, false), b(N, false);
    while (!b.at(cur)) {
        if (!a.at(cur)) {
            a.at(cur) = true;
            cf++;
        }
        else {
            b.at(cur) = true;
            cp++;
        }
        cur = A.at(cur);
    }
    if (cf - cp >= K) {
        cur = 0;
        for (int i  = 0; i < K; i++) {
            cur = A.at(cur);
        }
        cout << cur + 1 << endl;
        return 0;
    }
    long long M = (K - (cf - cp)) % cp;
    cur = 0;
    for (int i = 0; i < cf - cp + M; i++) {
        cur = A.at(cur);
    }
    cout << cur + 1 << endl;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int MOD = 1000000007;
const ll INF = 1LL << 60;
int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   string s, t;
   cin >> s >> t;
   bool flag = false;
   for(int i = 0;i < s.length();i++) {
      if(s[i]!=t[i]) flag = true;
   }
   if(flag) {
      cout << "No" << endl;
   }else {
      cout << "Yes" << endl;
   }
}

Measured memory_bytes: 3652
n, k = map(int,input().split())

pedras = list(map(int,input().split()))

INF = 1e12

dp = [INF] * n

dp[0] = 0
dp[1] = abs(pedras[1] - pedras[0])

for i in range(2,n):
    pulo = 0
    for j in range(i-1,-1,-1):
        pulo += 1
        if pulo > k:
            break
        else:
            dp[i] = min(dp[i], dp[j] + abs(pedras[i] - pedras[j]))


print(dp[n-1])


Measured memory_bytes: 84872
import sys
sys.setrecursionlimit(1000000)

INF = 1000000

N = int(input())
m = [INF] * 100001
m[0] = 0
m[1] = 1

def f(N):
    if m[N] != INF:
        return m[N]

    tmp = INF

    tmp = min(f(N - 1) + 1, tmp)

    a = 6
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 6

    a = 9
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 9

    m[N] = tmp
    return tmp

print(f(N))


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

int main()
{
	string s;
	cin >> s;
	int n = (int)s.length();
	bool first;
	if(s[0] == s[n-1]) {
		if(n % 2 == 0) first = true;
		else first = false;
	} else {
		if(n % 2 == 0) first = false;
		else first = true;
	}
	
	if(first) {
		puts("First");
	} else {
		puts("Second");
	}
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool cmp(pair<int,int> x, pair<int,int> y){
    return (abs(x.first-x.second) > abs(y.first-y.second));
} 
int main(int argc,char ** argv){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n;
  	cin >> n;
  	int h[n];
  	for(int i = 0 ; i < n ; i++)
  		cin >> h[i];
  	int dp[n];
  	dp[0] = 0;
 	dp[1] = abs(h[1] - h[0]);
  	for(int i = 2 ; i < n ; i++)
    {	
      	dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]) , dp[i - 2] + abs(h[i] - h[i - 2]));
      	//cout << dp[i] << endl;
    }
  	cout << dp[n - 1] << endl;
   
	return 0; 
}

Measured memory_bytes: 1024
IDENTIFICATION                   DIVISION.
       PROGRAM-ID.                      ABC_099_A.
       ENVIRONMENT                      DIVISION.
       DATA                             DIVISION.
       WORKING-STORAGE SECTION.
           01 N PIC 9(4).
       PROCEDURE                        DIVISION.
       MAIN.
           ACCEPT N FROM CONSOLE.
           IF 999 < N THEN
               DISPLAY "ABD" UPON CONSOLE
           ELSE
               DISPLAY "ABC" UPON CONSOLE
           END-IF.
           STOP RUN.


Measured memory_bytes: 636
N = int(input())
Nminus1 = N - 1
# lines = []

CSF = []
# S = [0 for _ in range(Nminus1)]
# F = [0 for _ in range(Nminus1)]

for i in range(Nminus1):
    c, s, f = input().split()
    CSF.append((int(c), int(s), int(f)))
    # C[i] = int(c)
    # S[i] = int(s)
    # F[i] = int(f)

# for line in lines:
#     c, s, f = line.split()
#     C.append(int(c))
#     S.append(int(s))
#     F.append(int(f))

ans = []

for i in range(Nminus1):
    a = 0
    for j in range(i, Nminus1):
        C, S, F = CSF[j]
        if a < S:
            a = S
        elif a % F == 0:
        	pass
        else:
            a += F - a % F
        a += C
    ans.append(a)

ans.append(0)
print('\n'.join(map(str, ans)))

Measured memory_bytes: 3064
n,k = map(int,input().split())

x = list(map(int,input().split()))
ans = 100000000000000

a = 0
while a != n:
	if x[a] >= 0:
		break
	a += 1
for i in range(max(0,a-k),n-k+1):
	if x[i+k-1] <= 0:
		ans = min(ans,-x[i])
	elif x[i] >= 0:
		ans = min(x[i+k-1],ans)
	else:
		ans = min(x[i+k-1]-x[i]+min(-x[i],x[i+k-1]),ans)
print(ans)

Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define F first
#define S second
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define pb push_back
#define fastIO ios::sync_with_stdio(0), cin.tie(0);
#define endl '\n'
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
int main() {
#ifdef LOCAL
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#else
    fastIO;
#endif
    ll n;
    cin >> n;
    string cad = to_string(n);
    int dig = 1 + floor(log10(1.0 * n));
    ll ans = 0;
    for (int mask = 0; mask < (1 << dig - 1); mask++) {
        int last = 0;
        for (int bit = 0; bit < dig - 1; bit++) {
            if (mask & (1 << bit)) {
                //cout << stoi(cad.substr(last, bit - last + 1)) << " ";
                ans += stoll(cad.substr(last, bit - last + 1));
                last = bit + 1;
            }
        }
        //cout << stoi(cad.substr(last, dig - last + 1))<<endl;
        ans += stoll(cad.substr(last, dig - last + 1));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int c = 1;
    int x;
    while (cin >> x, x) {
        printf("Case %d: %d\n", c++, x);
    }
}

Measured memory_bytes: 1136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;cin >> n >> k;
	vector<int> a(n);
	bool ans=false;
	rep(i,n) cin >> a.at(i);
	sort(a.begin(),a.end());
	if(n==1){
		if(a.at(0)==k) cout << "POSSIBLE" << endl;
		else cout << "IMPOSSIBLE" << endl;
		return 0;
	}
	int g=gcd(a.at(1),a.at(0));
	rep(i,n-2){
		g=gcd(a.at(i+2),g);
	}
	if(k%g==0 && k<=a.at(n-1)) ans=true;
	if(ans) cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
}

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

using namespace std;

    int main()
    {
        int a,b;
        cin>>a>>b;
        int c=a+b;
        if(a%3==0 || b%3==0 || c%3==0){
            cout<<"Possible"<<endl;
        }
        else cout<<"Impossible"<<endl;
        return 0;
    }




Measured memory_bytes: 256
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#include <bits/stdc++.h>
 
using namespace std;
 
int main(void) {
    string n;
    cin >> n;
    if(n[0] == '7' or n[1] == '7' or n[2] == '7'){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int>height(n);
    for(int i=0;i<n;i++){
        cin >> height[i];
    }
    for(int i=n-1;i>=1;i--){
        if(height[i]>=height[i-1])continue;
        if(height[i]+1==height[i-1])height[i-1]--;
        if(height[i]+1<height[i-1]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };
static const int mod = 1000000007;

int N;
int a[100005];

vector<int> A;
int ans;

signed main(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>a[i];
        A.push_back(a[i]);
    }
    sort(a,a+N);
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(), A.end()), A.end());

    queue<int> que;
    for(auto u:A)que.push(u);

    while(que.size()){
        int cost;
        int left,right;
        int b=que.front();
        left=lower_bound(a,a+N,b)-a;
        right=upper_bound(a,a+N,b)-a;
        cost=(right-left)-b;
        if(cost<0)cost=right-left;
        ans+=cost;
        que.pop();
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int cnt_digits(ll N){
 int digits=0;

 while(N>0){
 N/=10;
 digits++;
 }

 return digits;
 }

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

 int ans=cnt_digits(N); // 1*N=N max(cnt_digits(1),cnt_digits(N))=cnt_digits(N)

 for(ll A=1LL;A*A<=N;++A){
 if(N%A!=0) continue;
 const ll B=N/A;

 const int cur=cnt_digits(B);

 if(ans>cur){
 ans=cur;
 }
 }

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

Measured memory_bytes: 3468
#include <stdio.h>
#include <stdbool.h>
struct {
	bool stat;
	int subs;
}task[100000];
int main(void)
{
	int n, m, in;
	scanf("%d %d", &n, &m);
	char str[3];
	int penatly = 0, count = 0;
	while (m--)
	{
		scanf("%d %s", &in, str);
		if (task[in - 1].stat == false)
		{
			if (str[0] == 'A')
			{
				task[in - 1].stat = true;
				penatly += task[in - 1].subs;
				count++;
			}
			else if (str[0] == 'W')
			{
				task[in - 1].subs++;
			}
		}
	}
	printf("%d %d", count, penatly);
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define fi first
#define se second
#define double long double
using namespace std;
using ll = long long;

constexpr double PI = atan(1) * 4;

inline double ang(int x, int y) {
    double ret = atan2((double) y, (double) x);
    if(ret < 0) ret += 2 * PI;
    return ret;
}

inline double dist(double x, double y) {
    return sqrt(pow(x, 2) + pow(y, 2));
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    vector<pair<double, pair<double, double>>> v;
    for(int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        v.push_back({ang(x, y), {x, y}});
    }
    sort(v.begin(), v.end());
    double ans = 0.0;
    for(int i = 0; i < n; ++i) {
        double x = 0.0, y = 0.0;
        for(int j = 0; j < n; ++j) {
            int k = (i + j) % n;
            x += v[k].se.fi;
            y += v[k].se.se;
            ans = max(ans, dist(x, y));
        }
    }
    cout << setprecision(15) << fixed << ans << '\n';
}


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

using namespace std;

int n, k;
long long m, dp[305][305], dpp[305][305], ncr[305][305];

inline void add(long long &a, long long b, long long c) {
	a = b + c;
	if (a >= m)
		a -= m;
}

int main() {
	scanf("%d%d%lld", &n, &k, &m);
	for (int i = 0; i < 305; i++) {
		ncr[i][0] = ncr[i][i] = 1;
		for (int j = 1; j < i; j++)
			add(ncr[i][j], ncr[i - 1][j - 1], ncr[i - 1][j]);
	}
	n++;
	for (int i = 0; i <= k; i++)
		dp[1][i] = 1;
	for (int i = 2; i <= n; i++) {
		// for (int j = 0; j <= k; j++) printf("%lld%c", dp[i - 1][j], j == k ? '\n' : ' ');
		for (int j = k; j >= 0; j--)
			add(dpp[i - 1][j], dpp[i - 1][j + 1], dp[i - 1][j]);
		for (int j = 0; j < k; j++)
			for (int ii = 1; ii < i; ii++)
				dp[i][j] = (dp[i][j] + dp[i - ii][j] * dpp[ii][j + 1] % m * ncr[i - 2][ii - 1]) % m;
	}
	printf("%lld\n", dp[n][0]);
	return 0;
}


Measured memory_bytes: 2432
#include<stdio.h>
#define Max 100000
int partition(int p,int r,int*A);
int main()
{
  int i,q;
  int A[Max];
  int n;
  scanf("%d",&n);
  for(i=0;i<n;i++)  scanf("%d",&A[i]);
  q=partition(0,n-1,A);
  for(i=0;i<n;i++){
    if(i)printf(" ");
    if(i==q)printf("[");
      printf("%d",A[i]);
      if(i==q) printf("]");
    
  }printf("\n");
  return 0;
}
int partition(int p,int r,int *A){
  int x,i,j,tmp;
  x=A[r];
  i=p-1;
  for(j=p;j<r;j++){
    if(A[j]<=x){
      i++;
      tmp=A[i];
      A[i]=A[j];
      A[j]=tmp;
    }
  }
  tmp=A[i+1];
  A[i+1]=A[r];
  A[r]=tmp;
  return i+1;
}

Measured memory_bytes: 992
n = input()
l = len(n)
res = 0
for i in range(l):
    if i == 0 or i == 2 or i == 4:
        if l - i == 1:
            res += int(n)-10**i+1
        else:
            res += 10**(i+1) - 10**i
print(res)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
const ll INF = 1LL << 60;
const int k_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;
}

int main() {
	int N;
	cin >> N;
	map <string, ll> mp;
	rep( repeat, 0, N ){
		char input[ 11 ];
		cin >> input;
		sort( input, input + 10 );
		mp[ input ]++;
	}
	ll sum = 0;
	for(auto m:mp){
		ll num = m.second;
		sum += num*(num-1)/2;
	}
	cout << sum << endl;
}


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

int main(){
    int a,b,k;cin>>a>>b>>k;
    if(b-a+1<=2*k){
        for(int i=a;i<=b;i++) cout<<i<<endl;
    }
    else{
        for(int i=a;i<a+k;i++) cout<<i<<endl;
        for(int i=b-k+1;i<b+1;i++) cout<<i<<endl;
    }
}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl;
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    cin >> n;
    int b = 100000;
    rep(i, n)
    {
        b = b * 1.05;
        if (b % 1000 != 0)
        {
            b = (int)(b / 1000 + 1) * 1000;
        }
    }
    OP(b)
    return 0;
}


Measured memory_bytes: 2992
L,R = map(int,input().split())
P = 2019
if R - L > P:
    print(0)
else:
    Min = P
    for i in range(L,R):
        if Min ==0:
            break
        for j in range(i+1,R+1):
            tmp = (i*j)%P
            if tmp < Min:
                Min = tmp
    print(Min)

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int h, n, a[100000] = {},m=0;
    cin >> h >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        m += a[i];
    }
    if (m >= h) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vi2 = vector<vector<int>>;
using vb = vector<bool>;
using vb2 = vector<vector<bool>>;
using vc = vector<char>;
using vc2 = vector<vector<char>>;
using vs = vector<string>;
using si = set<int>;
using vs2 = vector<vector<string>>;
using pii = pair<int, int>;
using mii = map<int, int>;
const int INF = 1e9;
const ll LINF = 1e18;
const long double PI = acos(-1.0);
#define MP(a,b) make_pair((a),(b))
#define MT(...) make_tuple(__VA_ARGS__)
#define sz(x) (int)(x).size()
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
 
#define ALL(x) (x).begin(),(x).end()
#define SORT(v) sort(ALL(v));
#define IN(type,a) type a;cin >> a;
#define VIN(type,a,n) vector<type> a(n);cin >> a;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl;
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl;
#define COUT(x) cout << (x) << endl;
#define DCOUT(x,n) cout << fixed << setprecision(n) << (x) << endl;
#define ENDL cout << endl;
#define DB(s,x) cout << (s) << " : " << x << endl;

#define HOGE COUT("HOGE")

template<typename T>inline istream& operator>>(istream&i,vector<T>&v)
{REP(j,sz(v))i>>v[j];return i;}

template<typename T> bool chmax(T& a, const T& b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T& a, const T& b){if(a>b){a=b;return true;}return false;}
int main() {
    IN(char, s);
    
    if (s>='a') {
        s = 'a';
    }else{
        s = 'A';
    }
    COUT(s);
}


Measured memory_bytes: 3592
using System;
using System.Linq;
using static System.Math;
class Program {
    static void Main (string[] args) {
        var num = int.Parse (Console.ReadLine ());
        var vAry = Console.ReadLine ().Split (' ').Select (x => int.Parse (x)).ToArray ();
        var cAry = Console.ReadLine ().Split (' ').Select (x => int.Parse (x)).ToArray ();

        var ans = 0;

        for (var i = 0; i < num; i++) {
            if(vAry[i]>cAry[i])
            {
                ans += vAry[i] - cAry[i];
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define space " "
#define MOD (long long) 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename T> void __f(const char* variable_name, T&& value){cout << variable_name << ": " << value << endl;}
template <typename T1, typename... T2> void __f(const char* names, T1&& arg1, T2&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}

const ll N = 5e5 + 5;
ll *v;
ll n;

void solve(){
    cin >> n;
    ll ans = 0;
    ll x = n / 500;
    ans += x * 500;
    x = n / 5;
    ans += x * 5;
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    // cout << "\n\nBLAH BLAH BLAH\n\n";
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define For(n) for(int i=0;i<n;i++)
#define Forj(n) for(int j=0;j<n;j++)
#define pi 3.141592654
#define hell 1000000007
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fix(n) cout << fixed << setprecision(n)
#define in1(n,c) c n;cin>>n
#define in2(a,b,c) c a,b;cin>>a>>b
#define ina(a,n,c) c a[n];rep(i,0,n)cin>>a[i]
#define ins(s) string s;cin>>s
#define mset(a,n) memset(a,n,sizeof a)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
#define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
#define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
#define lbd lower_bound
#define ubd upper_bound
#define ll  long long
#define ull unsigned long long
#define ld long double
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define piii pair<pair<int,int>,int>
#define all(v) (v).begin(), (v).end()
#define sz(x) (ll)x.size()
#define out(n) cout<<n<<" "
#define outl(n) cout<<n<<endl
#define line cout<<endl

int main ()
{
   in1(n,int);
   if (n==1){
    cout<<1.0000000000;
   return 0;}
   if (n%2==0)
   {
       cout<<0.5000000000;
   }
   else {
        float a,b,c;
        int d;
   a=n;
   d=(n/2)+1;
   b=d;
    cout<<b/a;

   }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int n, w[101], i, j, l,ans[101], zenbu, heikin, a[101], b[101];
int main(void)
{
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &w[i]);
    }
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < i; j++)
        {
            a[i] += w[j];
        }
        for (l = i; l < n; l++)
        {
            b[i] += w[l];
        }
    }
    for (i = 0; i < n; i++)
    {
        ans[i] = a[i] - b[i];
        if (ans[i] < 0)
    {
        ans[i] = ans[i]*-1;
    }
    }
    
    qsort(ans, n, sizeof(int), compare_int);
    
    printf("%d", ans[0]);
}

Measured memory_bytes: 128
X, K, D = map(int, input().split())

if X == 0:
  if K % 2 == 0:
    print(0)
    exit()
  else:
    print(D)
    exit()



if abs(X // D) < K:
  K = K - abs(X // D)
  X = X - (X // D) * D
  if K % 2 == 0:
    print(abs(X))
  else:
    if X > 0:
      print(abs(X - D))
    else:
      print(abs(X + D))
else:
  if X > 0:
    print(abs(X - K * D))
  else:
    print(abs(X + D * K))

Measured memory_bytes: 9212
#include<stdio.h>

int main(){
  int n,ans;
  scanf("%d", &n);
  if(n<105){ans=0;}
  if(105<=n && n<135){ans=1;}
  if(135<=n && n<165){ans=2;}
  if(165<=n && n<189){ans=3;}
  if(189<=n && n<195){ans=4;}
  if(195<=n && n<201){ans=5;}
  printf("%d",ans);
  return 0;
}









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

using namespace std;

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

int main(void) {
  int N;
  cin >> N;
  vector<pair<int, int>> in(N);

  rep(i, N) cin >> in[i].first >> in[i].second;
  in.push_back({numeric_limits<int>::max(), 0});

  sort(in.begin(), in.end());

  int ans = in[0].first;
  rep(i, N) {
    ans += min(in[i + 1].first - in[i].first, in[i].second - in[i + 1].second);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[][] x = new int[n][d];
        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < x[i].length; j++) {
                x[i][j] = sc.nextInt();
            }
        }
        int integerNum = 0;
        for (int i = 0; i < x.length; i++) {
            for (int j = i + 1; j < x.length; j++) {
                int sum = 0;
                for (int k = 0; k < x[i].length; k++) {
                    sum += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
                }
                boolean isInteger = false;
                for (int k = 0; k <= sum; k++) {
                    if (k * k == sum) {
                        isInteger = true;
                    }
                }
                if (isInteger) {
                    integerNum++;
                }
            }
        }
        System.out.println(integerNum);
        sc.close();
    }
}

Measured memory_bytes: 23892
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		Arrays.sort(a);
		int tmp = a[n-1];
		int sub;
		int b = 0;

		//for (int i = 0; i < n; i++)
		//	System.out.println(a[i]);

		for (int i = 0; i < n; i++) {
			sub = Math.abs((a[n-1]+1)/2-a[i]);
			if (sub < tmp) {
				tmp = sub;
				b = i;
			}
		}

		System.out.println(a[n-1] + " " + a[b]);
	}
}


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

using namespace std;

int H, W;
int N;
set<int> B[200000];

int main() {
  cin >> H >> W >> N;
  for(int i = 0; i < N; ++i) {
    int x, y; cin >> x >> y; --x; --y;
    B[x].insert(y);
  }
  int r = 0;
  int x;
  for(x = 1; x < H; ++x) {
    if(B[x].upper_bound(r) != B[x].begin()) break;
    if(!B[x].count(r + 1)) ++r;
  }
  cout << x << endl;
  return 0;
}


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

int main()
{
  int A,B;
  cin >>A>>B;
  if(A+B==3){
    cout <<3<<endl;
  }else if(A+B==4){
    cout <<2<<endl;
  }else{
    cout <<1<<endl;
  }
}

Measured memory_bytes: 256
/*
Keep clam  Believe youself
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<cmath>
#define Xiaobo main
using namespace std;
const int maxn=2e5+7;
const int mod=1e9+7;
const double eps=1e-15;
const double pi=acos(-1);
const int INF=0x3f3f3f3f;
typedef long long ll;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;}
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}
//别急 dp找状态 问题看看本身的规律 贪心找方法
double sum[maxn];
double dp[maxn];
double a[maxn];
int Xiaobo()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		double x;
		cin>>x;
		a[i]=(1+x)*1.0/2;
	}
	for(int i=1;i<=n;i++) {
		sum[i]=sum[i-1]+a[i];
	}
	double l=0,r;
	l=sum[k];
	for(int i=k+1;i<=n;i++) {
		if(sum[i]-sum[i-k]>l) l=sum[i]-sum[i-k];
	}
	printf("%.10f\n",l);
	return 0;
}


Measured memory_bytes: 4480
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

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

    set<string> history;
    char c;
    for(int i=0; i<n; ++i){
        string s;
        cin >> s;
        if(i != 0 && c != s[0]){
            cout << "No" << endl;
            return 0;
        }
        c = s[s.size()-1];
        history.insert(s);
    }

    if(history.size() == n)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;

const int MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    long long K;
    cin >> K;

    long long j = s.size();
    chmin(j, K);

    for (int i = 0; i < j; i++) {
        if (s[i] != '1') {
            cout << s[i] << endl;
            return 0;
        }
    }
    cout << 1 << endl;
}

Measured memory_bytes: 256
//2020-07-31
#include <bits/stdc++.h>
using namespace std;
#define loop(v, st, en) for (int v = st; v < en; v++)
#define loopdesc(v, st, en) for (int v = st; v >= en; v--)
#define INF 1E9
#define clr(v, d) memset(v, d, sizeof(v))
#define P(x) cout << #x << " = { " << x << " }\n"
#define PI acos(-1)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
const int M = 2e5 + 5;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, cur = 300, total = 1000, stock = 0, s = -1, b = -1;
    cin >> n;
    ll arr[n+5];

    loop(i, 0, n) cin >> arr[i];
    loop(i, 0, n)
    {
        
        if (b == -1)
        {
            if (arr[i] <= cur)
                cur = arr[i];
            else
                b = cur;
        }
        if(b!=-1){
            if(arr[i]>=cur)cur= arr[i];
            else 
            s= cur ;
            if(i==n-1&& cur>b)s=cur;
        }
        if(s!=-1 &&b!= -1){
            stock = total / b ; 
            total -= stock * b;
            total += stock *s ; 
            stock =0 ;
            b=-1;
            s=-1;
            i--;
            cur =300;
        }
    }
    
    cout<<total <<endl;
    return 0;
}

Measured memory_bytes: 3616
N, X, Y = gets.split.map(&:to_i)

d = ->(x, y){[(y - x).abs, (X - x).abs + 1 + (y - Y).abs].min}
puts [*1 .. N].combination(2).each_with_object(Array.new(N, 0)){|(x, y), a| a[d[x, y]] += 1}.drop(1)

Measured memory_bytes: 1916
#include <bits/stdc++.h>
using namespace std;
int n, x, z;
int a[220], b[220], ac, bc, l[220];
bool g[220][220], v[220];
map<int, int> q;
bool P(int x) {
	if (x < 2) {
		return false;
	}
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}
bool dfs(int x) {
	for (int i = 0; i < bc; i++) {
		if (g[x][i] && !v[i]) {
			v[i] = true;
			if (l[i] == -1 || dfs(l[i])) {
				return l[i] = x, true;
			}
		}
	}
	return false;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		q[x] ^= 1;
		q[x + 1] ^= 1;
	}
	for (pair<int, int> i: q) {
		if (i.second == 0) {
			continue;
		}
		if (i.first & 1) {
			a[ac++] = i.first;
		} else {
			b[bc++] = i.first;
		}
	}
	for (int i = 0; i < ac; i++) {
		for (int j = 0; j < bc; j++) {
			if (P(abs(a[i] - b[j]))) {
				g[i][j] = true;
			}
		}
	}
	memset(l, -1, sizeof l);
	for (int i = 0; i < ac; i++) {
		memset(v, 0, sizeof v);
		if (dfs(i)) {
			z++;
		}
	}
	if ((ac - z) & 1) {
		z--;
	}
	printf("%d\n", ac + bc - z);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;string s;cin>>n>>s;
    int ans=0,cnt=0;
    for(auto a:s){
        if(a=='I') cnt++;
        else cnt--;
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF int(1e9+7)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

int a[100005], b[100005];

int main()
{
	IO_OP;
	int n;
	cin >> n;
	for(int i=0;i<n;i++) {
		int t;
		cin >> t;
		if(i&1)
			b[t]++;
		else
			a[t]++;
	}
	vector<pi> u, v;
	for(int i=0;i<100005;i++) {
		u.PB({a[i], i});
		v.PB({b[i], i});
	}
	sort(u.begin(), u.end());
	sort(v.begin(), v.end());
	reverse(u.begin(), u.end());
	reverse(v.begin(), v.end());
	if(u[0].S != v[0].S) {
		cout << n - (u[0].F + v[0].F) << endl;
	} else {
		cout << n - max(u[0].F + v[1].F, u[1].F + v[0].F) << endl;
	}
}


Measured memory_bytes: 2804
// ITP1_6_A Reversing Numbers

import java.util.Scanner;

class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int[] a;
      int n = Integer.parseInt(sc.next());
      if (n <= 100) {
         a = new int[n];
         for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sc.next());
         }
         for (int i = n - 1; i >= 1; i--) {
            System.out.print(a[i] + " ");
         }
         System.out.println(a[0]);
      }
   }
}

Measured memory_bytes: 17164
#include<stdio.h>
int main ()
{
    int m,n,arr[10001],c,i,d,sum=0,re;
    scanf ("%d %d",&m, &n);
    for (i=0;i<n;i++)
    {
        scanf ("%d",&arr[i]);

    }
    for (i=0;i<n;i++)
    {
        sum=arr[i]+sum;
    }
    c=m-sum;
    if (c>=0)
    {
        re=c;
    }
    else if (c<0)
    {
        re=-1;
    }
    printf ("%d\n",re);
    return 0;
}


Measured memory_bytes: 1716
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i;
	char a[100010];
	cin>>a;
	n=strlen(a);
	if(a[0]==a[n-1])
	{
		if(n%2==1)
		{
			cout<<"Second"<<endl;
		}
		else
		{
			cout<<"First"<<endl;
		}
	}
	else
	{
		if(n%2==1)
		{
			cout<<"First"<<endl;
		}
		else
		{
			cout<<"Second"<<endl;
		}
	}
}

Measured memory_bytes: 384
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{fastout, input, marker::Chars};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        x: i32,
        n: usize,
        mut p: [i32; n]
    }

    p.sort_by_key(|p| (p - x).abs());

    for i in 0.. {
        let t = x - i;
        if p.iter().find(|&&p| p == t).is_none() {
            println!("{}", t);
            break;
        }
        let t = x + i;
        if p.iter().find(|&&p| p == t).is_none() {
            println!("{}", t);
            break;
        }
    }
}


Measured memory_bytes: 2192
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define sz(x) (int)(x).size();
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
const int mod=1e9+7;
int32_t main()
{
	int n=in();
	string s1,s2;
	cin>>s1>>s2;
	int ans=3;bool back;
	for(int i=0;i<n;i++)
	{
	
		back=s1[i-1]==s2[i-1];
		if(s1[i]==s2[i]){if(back and i>0)ans*=2;}
		else
		{
			if(back)ans*=2;
			else ans*=3;
			i++;
		}
		ans%=mod;
	}
	cout<<ans;
	
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  cin>>N;
  vector<int>num(N);
  vector<int>point(N);
  vector<int>bonus(N-1);
  for(int i=0;i<N;i++){
    cin>>num.at(i);
  }
  for(int i=0;i<N;i++){
    cin>>point.at(i);
  }
  for(int i=0;i<N-1;i++){
    cin>>bonus.at(i);
  }
  int ans;
  ans=0;
  for(int i=0;i<N;i++){
    ans+=point.at(num.at(i)-1);
  }
  for(int i=0;i<N-1;i++){
    if((num.at(i)+1)==num.at(i+1)){
      ans+=bonus.at(num.at(i)-1);
    }
  }
  cout<<ans<<endl;
}

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

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

    vector<lint> x(n), y(n);
    for(lint i=0; i<n; i++)  cin >> x[i] >> y[i];

    vector<lint> v(n);
    iota(begin(v), end(v), 0);

    auto dist = [&](lint s, lint t) {
        lint dx = (x[s]-x[t])*(x[s]-x[t]);
        lint dy = (y[s]-y[t])*(y[s]-y[t]);
        return sqrt(dx + dy);
    };

    double ans = 0;
    do {
        for(lint i=0; i+1<n; i++)  ans += dist(v[i], v[i+1]);
    } while(next_permutation(begin(v), end(v)));

    for(double i=1; i <= n; i++) {
        ans /= i;
    }

    cout << setprecision(10) << ans << endl;
}

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

int main(){
  char s[200005];
  cin>>s;
  int l=0,r=strlen(s);
  while(s[l]!='A') ++l;
  while(s[r-1]!='Z') --r;
  cout<<r-l<<'\n';
}

Measured memory_bytes: 384
import math
n,d = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
def cheak(y,z):
    counter = 0
    for i in range(d):
        counter += (y[i]-z[i])**2
    if math.sqrt(counter).is_integer():
        return True
    return False
count = 0
for i in range(n):
    for k in range(i+1,n):
        if(cheak(x[i],x[k])):
            count+=1
print(count)

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

using namespace std;

constexpr int MAXV = 1e3 + 10;
constexpr long long INF = 1e12;

int main() {
  int n, w;
  cin >> n >> w;
  vector<long long> dp(n * MAXV, INF);
  dp[0] = 0;
  int weight, val;
  for (int i=0; i<n; ++i) {
    cin >> weight >> val;
    for (int x=dp.size()-1-val; x>=0; --x) {
      dp[x+val] = min(dp[x+val], dp[x] + weight);
    }
  }
  for (int i=dp.size()-1; i>=0; --i) {
    if (dp[i] <= w) {
      cout << i << "\n";
      break;
    }
  }
  return 0;
}


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

int main(){
	int n;
    cin>>n;
    vector<int> vec(n);
  	for(int i=0;i<n;i++){
    	cin>>vec[i];
    }
    int k=0;
    for(int i=0;i<n;i++){
       if(vec[i]!=i+1){
           k++;
       }
    }
    if(k<=2){
    	cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}


Measured memory_bytes: 256
N=int(input())
sosuu=[]
ans=[]
for i in range(2,55556):
    flag=True
    for s in sosuu:
        if i**0.5<s:
            break
        if i%s==0:
            flag=False
            break
    if flag:
        sosuu.append(i)
        if i%5==1:
            ans.append(i)
print(" ".join(map(str,ans[:N])))

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

int main() {
    int n; cin>>n;
    
    int a[n], b[n], c[n];
    for (int i=0; i<n; i++) {
        cin>>a[i];
        cin>>b[i];
        cin>>c[i];
    }

    int happ[n][3];

    happ[0][0] = a[0]; 
    happ[0][1] = b[0]; 
    happ[0][2] = c[0];
     

    for(int i=1; i<n; i++) {
        happ[i][0] = a[i] + max(happ[i-1][1], happ[i-1][2]);
        happ[i][1] = b[i] + max(happ[i-1][0], happ[i-1][2]);
        happ[i][2] = c[i] + max(happ[i-1][1], happ[i-1][0]);
    }

    int maxHapp = max(happ[n-1][0], max(happ[n-1][1],happ[n-1][2]));
    cout<<maxHapp<<'\n';


}

Measured memory_bytes: 2560
#include<iostream>

int main() {
	int n;
	std::cin >> n;
	double ans = 0, x;
	char u[4];
	for (int i = 0; i < n; i++) {
		std::cin >> x >> u;
		if (u[0] == 'B')x *= 380000;
		ans += x;
	}

	printf("%lf\n", ans);
}

Measured memory_bytes: 256
# 25

import sys
import itertools

sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    c_l = [[int(x) for x in input().split()] for y in range(h)]
    s_l = [[True] * w for x in range(h)]
    v_l = list(itertools.product([-1,0,1],repeat=2))
    
    def dfs(y, x):
        if x < 0 or y < 0 or x >=w or y >= h:
            return False
        if not s_l[y][x]:
            return False
        s_l[y][x] = False
        _c = c_l[y][x]
        if _c == 0:
            return False
        for _v in v_l:
            dfs(y+_v[0],x+_v[1])
        return True

    ans = 0
    for i in range(h):
        for j in range(w):
            if s_l[i][j]:
                if dfs(i, j):
                    ans += 1
                    
    print(ans)


Measured memory_bytes: 8028
N=list(map(int,input()))
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(4)] for _ in range(2)]
dp[0][0][0] = 1
for i in range(2):
    for j in range(4):
        for k in range(L):
            for d in range(10 if i else N[k]+1):
                fl = 1 if i == 1 or d < N[k] else 0
                cnt = j+1 if d != 0 else j
                if cnt > K:
                    continue
                dp[fl][cnt][k+1] += dp[i][j][k]
print(dp[0][K][L]+dp[1][K][L])

Measured memory_bytes: 9224
n = int(input())
count = 0
for i in range(1, n+1):
    stop = True
    c = 0
    while stop :
        if i % 2 == 0:
            c += 1
            i = i/2
        else:
            stop = False
    if c >= count :
        count = c
print(2**count)

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

int main(){
    int a,b;
    cin>>a>>b;
    
    if( a < b ) cout<<"a < b"<<endl;
    if( a == b ) cout<<"a == b"<<endl;
    if( a > b ) cout<<"a > b"<<endl;
    
}


Measured memory_bytes: 3120
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()
    a = i_input()

    print(n*n-a)

if __name__ == '__main__':
    main()


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


int main(){
	int n;
	cin >> n;
	int H[100] = {};
	for(int i = 0;i < n;i++){
		cin >> H[i];
	}
	int max = 0;
	int ans = 0;
	for(int j = 0;j < n;j++){
		if(H[j] >= max){
			ans++;
			max = H[j];
		}
	}
	cout << ans;
	return 0;
}


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

int main(){
  int a[45];
  int n;
  a[0] = a[1] = 1;
  cin >> n;
  for (int i=2;i<=n;i++){
    a[i] = a[i-1] + a[i-2];
  }
  cout << a[n] << endl;
  return 0;
}



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

using namespace std;

/* Plan
 * ----
 * Run through half of the smaller number to get al the common multiples, for each number check if its a divisor to both numbers
 * then check the corresponding larger multiple to see if it also works.
 *
 * The next step is to check how many are all coprimes of each other. We could use a loop
 */

// int main() {
    // long long int a, b;
    // vector<long long int> multiples;

    // cin >> a >> b;
    
    // multiples.push_back(1);
    // for (long long int i = 2; i <= sqrt(min(a, b)); i++)
    // {
        // if (a % i == 0 && b % i == 0)
        // {
            // bool coprime = true;
            // // Check if it's going to be co prime 
            // for (long unsigned int j = 1; j < multiples.size(); j++)
            // {
                // if (i % multiples[j] == 0) {
                    // coprime = false;
                    // break;
                // }
            // }
            
            // if (coprime) 
            // {
                // multiples.push_back(i);
            // }
        // }
    // }   

    // if (max(a, b) % (min(a, b) / multiples[multiples.size() - 1]) == 0 && multiples.size() != 1 && (min(a, b) / multiples[multiples.size() - 1]) != multiples[multiples.size() - 1])
    // {
        // bool coprime = true;
        // // Check if it's going to be co prime 
        // for (long unsigned int j = 1; j < multiples.size() - 1; j++)
        // {
            // if (min(a, b) / multiples[multiples.size() - 1] % multiples[j] == 0) {
                // coprime = false;
                // break;
            // }
        // }
        
        // if (coprime) 
        // {
            // multiples.push_back(min(a, b) / multiples[multiples.size() - 1]);
        // }
    // }
    
    // cout << multiples.size();
// }

long long gcd(long long a, long long b) {
	if (a < b) return gcd(b, a);
	if (b == 0) return a;
	return gcd(b, a % b);
}
bitset<1000001> bs;
vector<long long> primes;
void sieve() {
	bs.set();
	bs[0] = bs[1] = 0;
	for (long long i = 2; i <= 1000000; ++i) {
		if (bs[i]) {
			primes.push_back(i);
			for (long long j = i * i; j <= 1000000; j += i) bs[j] = 0;
		}
	}
}
int main() {
	sieve();
	long long A, B, ans = 1;
	scanf("%lld %lld", &A, &B);
	A = gcd(A, B);
	for (long long i: primes) {
		if (A % i == 0) ++ans;
		while (A % i == 0) A /= i;
	}
	if (A != 1) ++ans;
	printf("%lld", ans);
	return 0;
}


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

int main(){
  int n,k,q;   cin >> n >> k >> q;
  int a[q];
  rep(i,q) {
     cin >> a[i];
     }
  int b[n];
  rep(i,n){
     b[i] = k-q;
  }
  rep(i,q){
     b[a[i]-1]++;
  }
  rep(i,n){
     if(b[i] <= 0) cout << "No" <<endl;
     else cout << "Yes" << endl;
  }
}



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

def main():
    N = int(input())
    A = list(map(int, input().split()))

    i = 1
    ans = 0
    for a in A:
        if a == i:
            i += 1
        else:
            ans += 1
    if ans == N:
        print(-1)
    else:
        print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 25992
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(1, N_MAX + 1, 2))
    for i in range(1, int((N_MAX ** 0.5 - 1) / 2) + 1):
        if min_factor[i] != 2 * i + 1:
            continue
        for j in range(2 * i * (i + 1), len(min_factor), 2 * i + 1):
            if min_factor[j] > 2 * i + 1:
                min_factor[j] = 2 * i + 1

    def prime_factorize_fast(n):
        a = Counter()
        while not n & 1:
            a[2] += 1
            n //= 2
        while n != 1:
            a[min_factor[(n - 1) // 2]] += 1
            n //= min_factor[(n - 1) // 2]

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

    ans = 0
    for a in A:
        ans = (ans + pow(a, MOD - 2, MOD)) % MOD

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


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

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    long long int a[n];
    for (int i=0;i<n;i++) cin>>a[i];
    sort(a,a+n,greater<long long int>());
    vector <long long int> canbe;
    for (int i=0;i<n;i++){
        if(i==0) canbe.push_back(a[i]);
        else{
            canbe.push_back(a[i]);
            canbe.push_back(a[i]);
        }
    }
    long long int ans=0;
    for (int i=0;i<n-1;i++) ans+=canbe[i];
    cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 8988