akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	
	int n; cin >> n;
	vector<vi> a(n, vi(n));
	rep(i, n) rep(j, n) if(i != j) cin >> a[i][j];
	
	vector<vector<ll>> dp(n, vector<ll>(n, 1e18));
	vector<vector<ll>> ls(n, vector<ll>(n + 1));
	vector<vector<ll>> rs(n, vector<ll>(n + 1));
	
	rep(i, n) rep(j, n) rs[i][j + 1] = rs[i][j] + a[i][j];
	rep(i, n) rep(j, n) ls[i][j + 1] = ls[i][j] + a[j][i];
	
	ll ans = 1e18;
	dp[0][0] = 0;
	rep(j, n) rep(i, j + 1){
		vector<ll> sum(n + 1);
		for(int k = n - 1; k > j; k--) sum[k] = sum[k + 1] + rs[k][j] - rs[k][i];
		ll tmp = 0;
		for(int k = j + 1; k < n; k++){
			dp[j][k] = min(dp[j][k], dp[i][j] + tmp + sum[k]);
			tmp += ls[k][k] - ls[k][j];
		}		
		ans = min(ans, dp[i][j] + tmp);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7296
#include<stdio.h>
int main(){

int a,b;
char op;

while(1){
scanf("%d %c %d",&a,&op,&b);
if(op=='?')break;
if(op=='+'){
printf("%d\n",a+b);
}else if(op=='-'){
printf("%d\n",a-b);
}else if(op=='*'){
printf("%d\n",a*b);
}else if(op=='/'){
printf("%d\n",a/b);
}
}
return 0;
}


Measured memory_bytes: 2148
# define _CRT_SECURE_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <complex>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) begin(x),end(x)
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<":"<<x<<endl;
# define EPS 1e-12
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif
typedef long long lint;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
const int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
template<class T> void debug(T a) { for (auto i : a)cout << i << endl; }


int main()
{
	while (true)
	{
		INT(n); if (!n)break;
		int sc[60][40] = {};
		int m[60][60] = {};
		FOR(i, n)m[i][i]=1;
		FOR(bro, n)
		{
			INT(f);
			FOR(j, f)
			{
				INT(day);
				sc[bro][day] = 1;
			}
		}
		bool ok = false;
		FOR(day,40)
		{
			if (ok)break;
			FOR(bro, n)
			{
				if (sc[bro][day])
				{
					FOR(abro, n)
					{
						if (sc[abro][day])
						{
							FOR(k, n)
							{
								if (m[bro][k])m[abro][k] = 1;
							}
						}
					}
				}
			}
			FOR(bro, n)
			{
				int c = 0;
				FOR(abro, n)
				{
					c += m[bro][abro];
				}
				if (c == n)
				{
					cout << day << endl;
					ok = true;
					break;
				}
			}
		}
		if (!ok)cout << -1 << endl;
	}
}

Measured memory_bytes: 3028
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<pair<ll,ll>>>;

// MOD確認

ll N,K;

ll F(ll x){
    return (N+1)*x*(x+1) / 2 - x*(x+1)*(2*x+1) / 6 + x;
}

int main(){
    cin >> N >> K;
    cout << (F(N+1) - F(K-1)) % MOD << endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }


ll x;

int main(){
    cin >> x;
    vector<ll> ans(1,1);
    FOR(i,2,1001){
        for(ll j = i * i;j <= 1000;j *= i)ans.push_back(j);
    }
    sort(ALL(ans));
    // rep(i,5)cout << ans[i] << " ";
    // cout << endl;
    cout << *(upper_bound(ALL(ans),x) - 1) << endl;
}

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

int main(){
	string s;
	cin >> s;
	stack<char> sc;
	bool neko = true;
	for (int i = 0; i<s.length(); i++){
		if (s[i] == 'm' || s[i] == 'e' || s[i] == 'w'){
			sc.push(s[i]);
			if (sc.top() == 'w'){
				sc.pop();
				if (!sc.empty() && sc.top() == 'e'){
					sc.pop();
					if (!sc.empty() && sc.top() == 'm'){
						sc.pop();
					}
					else{
						sc.push('e');
						sc.push('w');
					}
				}
				else{
					sc.push('w');
				}
			}
		}
		else{
			neko = false;
			break;
		}
		if (sc.empty() && i != s.length() - 1){
			neko = false;
			break;
		}
	}
	if (neko&&sc.empty())
		cout << "Cat" << endl;
	else
		cout << "Rabbit" << endl;
}

Measured memory_bytes: 3228
import bisect
N = int(input())
A = list(map(int, input().split()))

s = [0]*N
s[0] = A[0]
for i in range(1, N):
    s[i] = s[i-1] + A[i]

id = bisect.bisect_left(s, s[-1] // 2)
if s[id] == s[-1] // 2:
    if s[-1] % 2 == 0:
        print(0)
    else:
        print(1)
else:
    k = 0
    if s[-1] % 2 != 0:
        k = 1
    ans = abs(s[id]*2 - s[-1])
    if id > 0:
        ans = min(ans, abs(s[id-1]*2 - s[-1]))
    print(ans)


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

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

    if (c == "a" or c == "i" or c == "e" or c == "u" or c == "o")
    {
        cout << "vowel" << endl;
    }
    else
    {
        cout << "consonant" << endl;
    }
}

Measured memory_bytes: 256
S = str(input())
if S[0] == 'R':
    if S[1] == 'R':
        if S[2] == 'R':
            print(3)
        else:
            print(2)
    else:
        print(1)
else:
    if S[1] == 'R':
        if S[2] == 'R':
            print(2)
        else:
            print(1)
    else:
        if S[2] == 'R':
            print(1)
        else:
            print(0)

Measured memory_bytes: 9052
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll run();
int main() {
#ifdef home
    freopen("i", "r", stdin);
    freopen("d", "w", stderr);
#endif
    cout.precision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    run();
    return 0;
}

ll run() {
    ll n;
    cin>>n;
    ll a[n+1],b[n+1];
    ll sum1=0,sum2=0;
    ll cnt=0;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        sum1+=a[i];
    }
    for(ll j=1;j<=n;j++){
        cin>>b[j];
        sum2+=b[j];
    }
    //cout<<sum1<<" "<<sum2<<"  ";
    vector<ll> v;
    sum1=0;sum2=0;
    for(ll i=1;i<=n;i++){
        if(a[i]<b[i]){
            cnt++;
            sum1+=(b[i]-a[i]);
        }
        else {
            sum2+=a[i]-b[i];
            v.emplace_back(a[i]-b[i]);
        }
    }
    if(sum1>sum2){
        cout<<"-1\n";
        return 0;
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    sum2=0;
    for(ll i=0;i<v.size();i++){
        if(sum2<sum1){
            sum2+=v[i];
            cnt++;
        }
    }
    cout<<cnt;
}








































Measured memory_bytes: 2936
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    int n, m;
    string name;
    map<string, int> data;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> name;
        if (data.count(name) > 0) {
            data[name] += 1;
        } else {
            data[name] = 1;
        }
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> name;
        if (data.count(name) > 0) {
            data[name] -= 1;
        } else {
            data[name] = -1;
        }
    }

    int v = 0;
    string s;
    for (auto i = data.begin(); i != data.end(); i++) {
        if (v < i -> second) {
            v = i->second;
            s = i-> first;
        }
    }

    cout << data[s] << endl;

   return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
  int n = 0;
  unsigned short *A, *B;
  int C[VMAX+1];
  int i = 0, j = 0;

  scanf("%d",&n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);
  
  for(i = 0; i < n; i++){
    scanf("%hu",&A[i+1]);
  }

  /*CountingSort*/
  for(i = 0; i <= VMAX; i++){
    C[i] = 0;
  }

  /*C[i]にiの出現回数を記録する*/
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }

  /*C[i]に以下の数の出現数を記録する*/
  for(i = 1; i <= VMAX; i++){
    C[i] = C[i] + C[i-1];
  }

  for(j = n; j > 0; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }

  /*end of Sort*/
  
  for(i = 1; i <= n; i++){
    printf("%d",B[i]);
    if(i < n)printf(" ");
    else printf("\n");
  }
  return 0;
}
/*
void CountingSort(int *A, int *B, int k){
  int i = 0;
  int j = 0;
  int C[N];

  for(i = 0; i <= k; i++){
    C[i] = 0;
  }
*/
  /*C[i]にiの出現回数を記録する
  for(j = 1; j <= n; j++){
    C[A[j]]++;
  }
  */
  /*C[i]に以下の数の出現数を記録する
  for(i = 0; i <= k; i++){
    C[i] = C[i] + C[i-1];
  }
  */
/* for(j = n; j > 0; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
}
*/



Measured memory_bytes: 9620
#include <iostream>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <algorithm>
#include <functional>
#include <cstring>
#include <limits.h>
#include <bitset>
#include <complex>
#include <cassert>
#define FOR(i,k,n)  for (int i=(k); i<(int)(n); ++i)
#define REP(i,n)    FOR(i,0,n)
#define FORIT(i,c)	for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define SZ(i) ((int)i.size())
#define GI(i) (scanf("%d",&i))
#define GLL(i) (scanf("%lld",&i))
#define GD(i)  (scanf("%lf",&i))
#define PB          push_back
#define MP          make_pair
#define MT          make_tuple
#define GET0(x)     (get<0>(x))
#define GET1(x)     (get<1>(x))
#define GET2(x)     (get<2>(x))
#define ALL(X)      (X).begin(),(X).end()
#define LLMAX       (1LL<<60)
#define LLMIN       -(1LL<<60)
#define IMAX        (1<<30)
#define IMIN        -(1<<30)
typedef long long LL;
using namespace std;

int main(void){
    LL N,M;
    GLL(N);GLL(M);
    LL ans=1;
    for(LL i=1;i*i<=M;i++){
        if(M%i==0 && N<=M/i)
            ans=max(i,ans);
        if(M%i==0 && N<=M/(M/i))
            ans=max(M/i,ans);
    }
    printf("%lld\n",ans);
    return 0;
}

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


vector<long long> LISLDS(long long N, long long A, long long B) {
    vector<long long> res;
    for (long long i = B-1; i >= 0; --i) res.push_back(i);
    if (A == 1) return res;
    long long rem = N - B;
    long long p = rem / (A-1);
    long long r = rem % (A-1);
    long long b = r;
    long long c = A-1-r;
    for (int i = 0; i < b; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p+1; ++j) {
            res.push_back(size + p - j);
        }
    }
    for (int i = 0; i < c; ++i) {
        int size = (int)res.size();
        for (int j = 0; j < p; ++j) {
            res.push_back(size + p-1 - j);
        }
    }
    return res;
}


int main() {
    long long N, A, B; cin >> N >> A >> B;
    if (A + B > N+1 || A * B < N) cout << -1 << endl;
    else {
        vector<long long> res = LISLDS(N, A, B);
        for (int i = 0; i < res.size(); ++i) {
            cout << res[i] + 1;
            if (i != (int)res.size() - 1) cout << " ";
        }
        cout << endl;
    }
}


Measured memory_bytes: 6128
import java.util.Scanner;

/**
 *
 * @author cs18097
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int lhigh = 0;
        int rlow = 1000000;
        int tmp;
        for(int i = 0;i < m;i++){
            tmp = sc.nextInt();
            if(lhigh < tmp)lhigh = tmp;
            tmp = sc.nextInt();
            if(rlow > tmp) rlow = tmp;
        }
        tmp = rlow-lhigh + 1;
        if(tmp < 0) tmp = 0;
        System.out.print(tmp);
    }
    
}


Measured memory_bytes: 62260
//解説に倣って二分探索
#include<bits/stdc++.h>
using namespace std;

int main(){
  int64_t n,m;
  cin>> n >> m;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin>>a[i];
  sort(a.begin(),a.end());
  
  int64_t l=2*a[0],r=2*a[n-1]+1,cl=n*n,cr=0;
  while(r-l>1){
    int64_t x=(l+r)/2,count=0;
    for(int left_hand=n-1,right_hand=0; left_hand>=0 && right_hand<n; left_hand--){
      while(right_hand<n && a[left_hand]+a[right_hand]<x) right_hand++;
      count+=n-right_hand;
    }
    if(count<m){ r=x; cr=count;}
    else{ l=x; cl=count;}
  }
  
  vector<int64_t> s(n);
  s[n-1]=a[n-1];
  for(int i=n-2; i>=0; i--) s[i]=s[i+1]+a[i];
  int64_t ans=0;
  for(int left_hand=n-1,right_hand=0; left_hand>=0; left_hand--){
    while(right_hand<n && a[left_hand]+a[right_hand]<l) right_hand++;
    if(right_hand>=n) break;
    ans+=a[left_hand]*(n-right_hand) + s[right_hand];
  }
  ans-=l*(cl-m);
  cout<< ans <<endl;
}
//累積和とか計算量とか違うかもしれない
//オーバーフロー？ int型はおよそ2e+9まで

Measured memory_bytes: 4544
A,B,K=map(int,input().split())
if K<=A:
    print(A-K,B)
elif A<K<=A+B:
    print(0,A+B-K)
else:
    print(0,0)


        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














Measured memory_bytes: 8988
<?php

fscanf(STDIN, "%d %d", $n, $k);
$X = array_map('intval', explode(' ', trim(fgets(STDIN))));
const X_MAX = 100000005;
$X[] = -1 * X_MAX;
$X[] = X_MAX;
sort($X);

$l = 0;
$r = count($X);
while ($r - $l >= 1) {
    $mid = intdiv($r + $l, 2);
    if ($X[$mid] > 0) {
        $r = $mid;
    } else {
        $l = $mid + 1;
    }
}
$start = $r;

$ans = PHP_INT_MAX;
$r = 1;
for ($l = 1; $l <= $n; ++$l) {
    while ($r <= $n && $r - $l < $k) {
        ++$r;
    }
    if ($r - $l !== $k) break;

    // 左端 $l; 右端 $r - 1;
    if ($X[$l] < 0 && $X[$r - 1] > 0) {
        // -+
        $ans = min($ans, abs(2 * $X[$l]) + $X[$r - 1]);
        $ans = min($ans, abs($X[$l]) + 2 * $X[$r - 1]);
    } else {

        if (!($X[$l - 1] < 0) || !($X[$r] > 0)) continue;

        /* echo "l: $l, r: $r, start: $start", PHP_EOL; */

        // --
        // ++
        if ($X[$r - 1] >= 0) {
            $ans = min($ans, $X[$r - 1]);
        } else {
            $ans = min($ans, abs($X[$l]));
        }
    }
}

echo $ans, PHP_EOL;


Measured memory_bytes: 16884
from collections import deque
from copy import deepcopy

h, w = map(int, input().split())
mazemother = []
for i in range(h):
    s = input()
    mazemother.append(list(s))
ans = 0

def mazemax(px, py):
    global ans
    maze = deepcopy(mazemother)
    dp = [[-1] * w for i in range(h)]
    dp[py][px] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    pos = deque([[px, py]])

    while len(pos) > 0:
        x, y = pos.popleft()
        maze[y][x] = "#"
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] == "." and dp[ny][nx] == -1:
                dp[ny][nx] = dp[y][x] + 1
                pos.append([nx, ny])
    for i in range(w):
        for j in range(h):
            ans = max(ans, dp[j][i])


for i in range(w):
    for j in range(h):
        if mazemother[j][i] == ".":
            mazemax(i, j)
print(ans)

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

using namespace std;
using ll = long long;
using IP = pair<int, int>;

const ll linf = 1LL << 62;
const int inf = 99999999;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
const ll atcoder = 1e9 + 7;

#define Endl endl
#define mp make_pair
#define all(v) v.begin(),v.end()
#define pb push_back
#define pr(x) cout << x << endl
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define rep(i,n) for(int i= 0;i<n;i++)

ll gcd(ll a, ll b) {//最大公約数
	if (a%b == 0)return b;
	else gcd(b, a%b);
}

ll lcm(ll a, ll b) {//最小公倍数
	return (a / gcd(a, b))*b;
}

int main(){

	string a, b;
	cin >> a >> b;
	a += b;
	int c = stoi(a);

	rep(i, 1000) {
		if (c == i*i) {
			pr("Yes");
			return 0;
		}
		if (i*i > c)break;
	}
	pr("No");

	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 998244353
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

struct edge{lint to,cost;};
lint V;
vector<edge> G[200000]; // MAX_V
lint d[200000]; // MAX_V
void dijkstra(lint S){
  priority_queue<plint,vector<plint>,greater<plint>> que;
  fill(d,d+V,LINF);

  d[S]=0;
  que.push(plint(0,S));
  while(!que.empty()){
    pint p=que.top();
    que.pop();
    lint v=p.second;
    if(d[v]<p.first) continue;
    rep(i,G[v].size()){
      edge e=G[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.push(plint(d[e.to],e.to));
      }
    }
  }
}

int main(void){
    lint M;
    cin >> V >> M;
    rep(i,V-1){
        edge in;
        in.to=i,in.cost=0;
        G[i+1].push_back(in);
    }
    rep(i,M){
        edge in;
        lint x,y,c;
        cin >> x >> y >> c;
        x--,y--;
        in.to=y,in.cost=c;
        G[x].push_back(in);
    }
    dijkstra(0);
    if(d[V-1]==LINF) cout << -1 << endl;
    else cout << d[V-1] << endl;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s,s2; cin>>s>>s2;
	s+=s2;
	int a=stoi(s);
	int i=2;
	while(i*i<=a)++i;
	cout<<(--i*i==a?"Yes"s:"No"s)<<"\n"s;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 100005

int N,W;
int count_table[NUM];
int ans[NUM];
vector<int> G[NUM];

int main(){

	scanf("%d %d",&N,&W);

	//約数の集合を作る
	for(int base = 1; base <= N; base++){
		for(int to = base; to <= N; to += base){
			G[to].push_back(base);
		}
	}

	for(int i = 1; i <= N; i++){
		count_table[i] = 0;
	}

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

		for(int k = 0; k < G[i].size(); k++){
				count_table[G[i][k]]++;
		}
		count_table[i] += 2;
	}

	ans[1] = W;
	int tmp_num = W;

	for(int left = 2; left <= N-W+1; left++){

		count_table[left-1] -= 2;
		if(count_table[left-1] < 2)tmp_num--;

		for(int i = 0; i < G[left-1].size(); i++){

			count_table[G[left-1][i]]--;
			if(count_table[G[left-1][i]] == 1){
				tmp_num--;
			}
		}

		tmp_num++;
		count_table[left+W-1] += 2;

		for(int i = 0; i < G[left+W-1].size(); i++){
			count_table[G[left+W-1][i]]++;
			if(count_table[G[left+W-1][i]] == 2){

				tmp_num++;
			}
		}
		ans[left] = tmp_num;
	}

	printf("%d",ans[1]);

	for(int i = 2; i <= N-W+1; i++){
		printf(" %d",ans[i]);
	}
	printf("\n");

	return 0;
}



Measured memory_bytes: 14252
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define deb(x) cout << #x << " is " << x << "\n";

using namespace std;
using namespace __gnu_pbds;

const double PI = 2 * acos(0.0);
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
  	cin >>s;
    int ans = 0, i = 0, j = s.size() - 1;
    while(i < j){
        if(s[i] != s[j])
            ans++;
        i++;
        j--;
    }
    cout <<ans;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

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

int main(void){
  int i,n,a,b,c;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d %d\n",&a,&b,&c);
    if(max(a,b,c)==a){
      if(a*a==b*b+c*c) printf("YES\n");
      else printf("NO\n");
    }
    else if(max(a,b,c)==b){
      if(b*b==a*a+c*c) printf("YES\n");
      else printf("NO\n");
    }
    else{
      if(c*c==a*a+b*b) printf("YES\n");
      else printf("NO\n");
    }
  }
  return 0;
}


Measured memory_bytes: 1624
#include<bits/stdc++.h>
using namespace std;
int n;
map<string,int>mp;
vector<string>ans;
int mx=0;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++) {
		string s;
		cin>>s;
		mp[s]++;
	}
	for(map<string,int>::iterator i=mp.begin();i!=mp.end();i++)
		if(i->second>mx) {
			mx=i->second;
			ans.clear();
			ans.push_back(i->first);
		}
		else if(i->second==mx) ans.push_back(i->first);
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl;
	return 0;
}

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

int main() {
  int K;
  string S;
  cin >> K >> S;
  
  if(S.size() > K){
    for(int i=0; i<K; i++){
      cout << S.at(i);
    }
    cout << "..." << endl;
  }
  
  else{
    cout << S << endl;
  }
}


Measured memory_bytes: 3632
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
#include<iomanip>
using namespace std;
using ll=long long;

int main(){
    int n;
    cin>>n;
    vector<double> x(n),y(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];

    vector<int> perm(n);
    iota(perm.begin(),perm.end(),0);
    double sum=0;
    int cnt=0;
    do{ 
        double res=0;
        for(int i=0;i+1<n;i++){
            res+=sqrt((x[perm[i]]-x[perm[i+1]])*(x[perm[i]]-x[perm[i+1]])+(y[perm[i]]-y[perm[i+1]])*(y[perm[i]]-y[perm[i+1]])+1e-10);
        }
        sum+=res;
        cnt++;
        
    }while(next_permutation(perm.begin(),perm.end()));

    cout<<fixed<<setprecision(10);
    cout<<sum/cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cfloat>
#define zero(x) (((x)>0?(x):-(x))<eps)

#define pause cout << " press ansy key to continue...",  cin >> chh
#define file_r(x) freopen(x,  "r",  stdin)
#define file_w(x) freopen(x,  "w",  stdout)
#define lowbit(x) ((x) & (-x))

#define repit(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, j, n, m) rep(i, n) rep (j, m)
#define repe(i, u) for (int i = head[u]; i != -1; i = nxt[i])
#define repd(i, n) for (int i = (n - 1); i >= 0; i--)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
#define FORD(i, n, m) for (int i = (n); i >= (m); i--)

#define pb push_back
#define X first
#define Y second
#define ins insert
#define rb rbegin
#define be begin
#define er erase
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define SZ(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define sqr(r) ((r) * (r))
#define dis(x1, y1, x2, y2) (((x1) - (x2)) * ((x1) - (x2)) + ((y1) - (y2)) * ((y1) - (y2)))
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

#define sc(x) cout << #x" = " << x << endl, system("pause")
#define sc2(x, y) cout << #x" = " << x << " " << #y" = " << y << endl, system("pause")
#define sc3(x, y, z) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << endl, system("pause")
#define sc4(x, y, z, w) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << " " << #w" = " << w << endl, system("pause")
#define sca(A, n, m) {                      \
  rep(i, n){                                    \
        rep(j, m - 1) cout << A[i][j] << " ";     \
        cout << A[i][m-1] << endl;              \
    }                                           \
}
#define sca1(A, n, m) {                    \
    FOR(i, 1, n){                                \
        FOR(j, 1, m-1) cout << A[i][j] << " ";   \
        cout << A[i][m] << endl;                \
    }                                           \
}

#define in(n) scanf("%d", &n)
#define in2(n, m) scanf("%d %d", &n, &m)
#define in3(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define in4(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)

using namespace std;
int chh;

typedef vector<int> vi;
typedef set<int> si;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<int, pii> pi3;
typedef vector< pair<int, int> > vpii;
typedef long long LL;

string s;

bool gao() {
    int n = SZ(s);
    rep (i, n) {
        if (s[i] != 'C') continue;
        FOR (j, i + 1, n - 1) {
            if (s[j] == 'F') return 1;
        }
    }
    return 0;
}

int main() {
    while (cin >> s) puts(gao() ? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> k(M);
  vector<vector<int>> s(M);
  for (int i = 0; i < M; i++){
    cin >> k[i];
    for (int j = 0; j < k[i]; j++){
      int x;
      cin >> x;
      x--;
      s[i].push_back(x);
    }
  }
  vector<int> p(M);
  for (int i = 0; i < M; i++){
    cin >> p[i];
  }
  int ans = 0;
  for (int i = 0; i < (1 << N); i++){
    bool flg = true;
    for (int j = 0; j < M; j++){
      int count = 0;
      for (int l = 0; l < k[j]; l++){
        if ((i >> s[j][l]) & 1){
          count ++;
        }
      }
      if (count % 2 != p[j]){
        flg = false;
      }
    }
    if (flg){
      ans++;
    }
  }
  cout << ans << endl;
}

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

mod = 10**9+7


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

    r1 = [1]
    r2 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
        r2.append(r2[i] * (N-1-i) % mod)
    r2.reverse()

    ans = 0
    r = 0
    for i in range(N-1):
        r += r1[i] * r2[i+1]
        ans += (X[i+1] - X[i]) * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


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

int main()
{
	ll t1,t2,a1,a2,b1,b2;
	scanf("%lld %lld",&t1,&t2);
	scanf("%lld %lld",&a1,&a2);
	scanf("%lld %lld",&b1,&b2);
	ll a=a1-b1,b=a2-b2;
	if(a<0)
	{
		a=-a,b=-b;
	}
	ll sum=a*t1+b*t2;
	if(sum==0)
	{
		puts("infinity");
		return 0;
	}
	if(sum>0)
	{
		puts("0");
		return 0;
	}
	ll ret=a*t1/(-sum)+(-b)*t2/(-sum);
	if((-b)*t2%(-sum)==0) ret--;
	printf("%lld\n",ret);
	return 0;
}

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

int main()
{
  ll n,mx=0;
  cin>>n;
  string s;
  map<string ,ll>m;
  for(ll i=0;i<n;i++)
  {
    cin>>s;
    m[s]++;
    mx=max(mx,m[s]);
    
  }
  for(auto u:m)
  {
    if(u.second==mx)cout<<u.first<<"\n";
  }
  
  
  
  
 
  
  
  
  
}


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

int mutu(int a,int b){
    if(a<=1) return 0;
    else return (mutu(a-1,b)+b)%a;
}

int main(){
    int a,b;
    while(1){
        cin>>a>>b;
        if(a==0&&b==0) break;
        cout<<mutu(a,b)+1<<endl;
    }
    return 0;
}


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

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        --x;
        a[i] = x;
    }
    vector<ll> num;
    set<ll> st;
    num.emplace_back(0);
    st.insert(0);
    ll now = 0;
    while (true) {
        now = a[now];
        if (st.count(now)) break;
        num.emplace_back(now);
        st.insert(now);
    }
    ll start = 0;
    for (int i = 0; i < num.size(); ++i) {
        if (num[i] == now) {
            start = i;
        }
    }
    if (k < start) cout << num[k] + 1 << endl;
    else cout << num[start + (k - start) % ((ll)(st.size()) - start)] + 1 << endl;
}


Measured memory_bytes: 15464
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

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

main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k, x0, y0, x1, y1;
    cin >> n >> m >> k;
    cin >> x0 >> y0 >> x1 >> y1;
    --x0, --y0, --x1, --y1;
    vector <string> a(n);
    for (auto &i : a) cin >> i;
    vector <vector <int> > d(n, vector <int> (m, INF));
    d[x0][y0] = 0;
    queue <pii> q;
    q.push({x0, y0});
    while (!q.empty()) {
        int x, y;
        tie(x, y) = q.front();
        q.pop();
        for (int di = 0; di < 4; di++) {
            for (int i = 1; i <= k; i++) {
                int tox = x + dx[di] * i, toy = y + dy[di] * i;
                if (inside(tox, toy, n, m)) {
                    if (a[tox][toy] == '@') break;
                    if (d[tox][toy] == INF) {
                        d[tox][toy] = d[x][y] + 1;
                        q.push({tox, toy});
                    }
                    if (d[tox][toy] <= d[x][y]) break;
                }
            }
        }
    }
    if (d[x1][y1] >= INF) cout << "-1\n";
    else cout << d[x1][y1] << '\n';
}


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

typedef long long ll;

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

  vector<int> v(n);
  iota(v.begin(),v.end(),1);
  do {
    for(int i=0; i<v.size(); i++){
      if(i!=0) cout <<" ";
      cout << v[i];
    }
    cout << endl;
  } while(next_permutation(v.begin(),v.end()));

}


Measured memory_bytes: 3084
use std::io;
use std::str::FromStr;

fn input_int_tuple() -> (i32, i32, i32) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<i32> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1], vec[2])
}


fn main() {
    let (a1, a2, a3) = input_int_tuple();
    let (d1, d2, d3) = ((a1 - a2).abs(), (a2 - a3).abs(), (a3 - a1).abs());
    let mut max = 0;
    if max < d1 {
        max = d1;
    }
    if max < d2 {
        max = d2;
    }
    if max < d3 {
        max = d3;
    }
    println!("{}", d1 + d2 + d3 - max);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF 2 << 29
#define MOD 1000000007
#define Yes(f) puts((f)? "Yes" : "No")
#define YES(f) puts((f)? "YES" : "NO")
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
using Graph = vector<vector<int>>;

int main(){
    int a, b, i, tap;
    cin >> a >> b;
    tap = 1;
    for(i = 0; tap < b; i++){
        tap += a - 1;
    }
    cout << i << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<stdio.h>
#include<utility>//swapでaとbの値を入れ替える
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
using namespace std;
int abc(int a,int b) {
	int x = 0;
	for (int i = b; i <= a; i++) {
		for (int j = b; j <= a; j++) {
			if (j % i >= b)x++;
		}

	}
	return x;
}

int main() {
	int a,b;
	cin >> b >> a;
	if (b % 500 <= a)cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
double dp[1100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	dp[0]=1;
	for(int i=0;i<a;i++){
		double ks=1;
		for(int j=1;j<=b&&i+j<=a;j++){
			dp[i+j]+=dp[i]*ks/(a-i-j+1);
			ks*=(double)(a-i-j)/(a-i-j+1);
		}
	}
	printf("%.12f\n",dp[a]);
}

Measured memory_bytes: 1076
#include<bits/stdc++.h>
using namespace std;
bitset<4000010> f;
int main()
{
	int n,sum;
    cin>>n;
    int a;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
      cin>>a;
      f|=f<<a;
      sum+=a;
    }
    for(int i=(sum+1)/2;i<=sum;i++)
    	if(f[i])
	    {
	       cout<<i<<endl;
	       break;
	    }
    return 0;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int, input().split()))
ans = 'APPROVED'

for i in range(n):
  if a[i]%2==0:
    if a[i]%3==0 or a[i]%5==0:
        continue
    else:
      ans='DENIED'
      break
  else:
    continue
print(ans)

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

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define MIN(a,b) ((a)>(b)? (b): (a))
#define MAX(a,b) ((a)<(b)? (b): (a))

const long long INF = 1LL << 60;
typedef unsigned long long ll;
const long long MOD = 1000000000 + 7;

int main(){
    int n;
    cin >> n;
    if(n/10==9 || n%10==9)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3588
#include<cstdio>
#include<vector>
#include<map>
#include<set>

using namespace std;

long long n;
map<long long, vector<long long>> m;
set<long long> ans;

void check_k(long long a, long long b) {
  if (b % a == 1) {
    ans.insert(a);
  }
  for (auto k: m[a]) {
    if (b % k == 1) {
      ans.insert(k);
    }
  }
}

int main() {
  scanf("%lld", &n);
  for (int i = 2; 1ll * i * i <= n; i++) {
    for (long long j = 1ll * i * i; j <= n; j *= i) {
      m[j].push_back(i);
    }
  }
  ans.insert(n);
  for (auto k: m[n]) {
    ans.insert(k);
  }
  if (n != 2) {
    ans.insert(n - 1);
  }
  for (int i = 2; 1ll * i * i <= n; i++) {
    if (n % i == 0) {
      check_k(i, n / i);
      check_k(n / i, i);
    }
  }
  for (int i = 2; 1ll * i * i <= (n - 1); i++) {
    if ((n - 1) % i == 0) {
      ans.insert(i);
      ans.insert((n - 1) / i);
    }
  }
  printf("%d\n", ans.size());
}


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

int main(){
  int A,B,C;
  int D,E,F;
  int G,H,I;
  cin>>A>>B>>E; 
  G=A+B-E;  // G=A+B+C-E-C;
  F=A+G-E;  // F=A+D+G-D-E
  I=E+G-F;  // I=C+E+G-C-F
  H=A+E-G;
  C=E+I-B;
  D=E+I-G;
  cout<<A<<' '<<B<<' '<<C<<endl;
  cout<<D<<' '<<E<<' '<<F<<endl;
  cout<<G<<' '<<H<<' '<<I<<endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = LLONG_MAX;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */


int main() {
    int n,k;cin >>  n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    resort(a);
    int ans = 0;
    rep(i, k) ans += a[i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string tenki;
  char maetenki='R';
  int count =0;
  int i=0;
 
  cin >>  tenki;
  while(i<3){
  if(tenki.at(i)=='S'||tenki.at(i)=='R'){
 if(tenki.at(i)=='R'){
   if(count==0){
   count++;
   }
   else{
     if(maetenki==tenki.at(i)){
       count++;
     }
        }
  }
    maetenki=tenki.at(i);
    i++;
  }
  }
  cout << count << endl;
}
  
  

Measured memory_bytes: 3612
from heapq import heappush, heappop

def solve():
    S = input()
    K = int(input())
    L = len(S)
    INF = 10**9
    cost = [[INF]*(L+1) for i in range(L+1)]
    cost[0][L] = 0
    ss = []
    que = [(0, 0, L)]
    while que:
        d, a, b = heappop(que)
        if cost[a][b] < d:
            continue
        ss.append((a, b))
        if a+1 == b:
            if d+1 < cost[a+1][b]:
                cost[a+1][b] = d + 1
            continue
        if S[a] == S[b-1]:
            if d+2 < cost[a+1][b-1]:
                cost[a+1][b-1] = d + 2
                if a+1 < b-1:
                    heappush(que, (d+2, a+1, b-1))
        else:
            if d+2 < cost[a+1][b]:
                cost[a+1][b] = d + 2
                if a+1 < b:
                    heappush(que, (d+2, a+1, b))
            if d+2 < cost[a][b-1]:
                cost[a][b-1] = d + 2
                if a < b-1:
                    heappush(que, (d+2, a, b-1))
    ln = min(cost[i][i] for i in range(L+1))
    ss.reverse()
    dp = [[0]*(L+1) for i in range(L+1)]
    for i in range(L+1):
        if cost[i][i] == ln:
            dp[i][i] = 1
    for a, b in ss:
        d = cost[a][b]
        r = 0
        if a+1 == b:
            if d+1 == cost[a+1][b]:
                r = dp[a+1][b]
        else:
            if S[a] == S[b-1]:
                if d+2 == cost[a+1][b-1]:
                    r = dp[a+1][b-1]
            else:
                if d+2 == cost[a+1][b]:
                    r += dp[a+1][b]
                if d+2 == cost[a][b-1]:
                    r += dp[a][b-1]
        dp[a][b] = r
    if dp[a][b] < K:
        print("NONE")
        return True
    SL = []; SR = []
    a = 0; b = L
    while a < b:
        if a+1 == b:
            assert cost[a][b]+1 == cost[a+1][b]
            SL.append(S[a])
            a += 1
            continue
        if S[a] == S[b-1]:
            assert cost[a][b]+2 == cost[a+1][b-1]
            SL.append(S[a])
            SR.append(S[b-1])
            a += 1; b -= 1
        elif S[a] < S[b-1]:
            c = (cost[a][b]+2 == cost[a+1][b])
            if c and K <= dp[a+1][b]:
                SL.append(S[a])
                SR.append(S[a])
                a += 1
            else:
                if c:
                    K -= dp[a+1][b]
                SL.append(S[b-1])
                SR.append(S[b-1])
                b -= 1
        else:
            c = (cost[a][b]+2 == cost[a][b-1])
            if c and K <= dp[a][b-1]:
                SL.append(S[b-1])
                SR.append(S[b-1])
                b -= 1
            else:
                if c:
                    K -= dp[a][b-1]
                SL.append(S[a])
                SR.append(S[a])
                a += 1
    SR.reverse()
    SL.extend(SR)
    print("".join(SL))
solve()


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

using namespace std;

const int N = 2 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n, m;
int u[N], d[N];
string s[N];

bool read() {
    if (!(cin >> n >> m))
        return false;

    for (int i = 0; i < n; ++i)
        cin >> s[i];

    return true;
}

void solve() {
    for (int i = 0; i < m; ++i)
        u[i] = -1, d[i] = 0;

    auto ans = 1;

    for (int i = 0; i < n; ++i)
        for (int j = 0, l = -1, r = 0; j < m; ++j)
            if (s[i][j] == '.') {
                if (r <= j) for (l = j, r = j; r < m && s[i][r] == '.'; ++r) { }
                if (d[j] <= i) for (u[j] = i, d[j] = i; d[j] < n && s[d[j]][j] == '.'; ++d[j]) { }
                ans = max(ans, r - l + d[j] - u[j] - 1);
            }

    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 4608
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a[3],b[3];
  int c[5];fill(c,c+5,0);
  for(int i=0;i<3;i++){
    cin>>a[i]>>b[i];
    c[a[i]]++;
    c[b[i]]++;
  }
  for(int i=1;i<=4;i++){
    if(c[i]>=3){
      cout<<"NO"<<endl;
    return 0;
    }
  }
  cout<<"YES"<<endl;
}


Measured memory_bytes: 256
/*---------------------------*\
____________Mari000____________         
________Mostafa  Shehab________    
\*---------------------------*/

#include <bits/stdc++.h>
using namespace std;
 
#define PI  3.14159265  // PI = acos(-1)
#define EPS (1e-10)
#define endl "\n"
typedef long long ll;
typedef long double ld;
//template <class Type>

ll power(ll x,ll y,ll p);
int Bit(ll x);
 
inline int D(){
	int t;
	scanf("%d",&t);
	return t;
}
inline ll llD(){
	ll t;
	scanf("%lld",&t);
	return t;
}

const int N=1e5 + 5;
unordered_map<int,int> mp;
int n;
ll cnt=1e18,m;


int i;
int a,b,c,d,sum;

int main(){
	int n=D();
	for(i=1;sum<n;++i)
		sum+=i;
	--i;
	if(sum-n <= i)
		printf("%d",i);
	else
		printf("%d",i-1);

}










ll power(ll x,ll y,ll p){ 
    ll res = 1;      // Initialize result 
  
    x = x % p;  // Update x if it is more than or  
                // equal to p 
    while (y > 0){ 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p; 
  
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;
    }
    return res; 
}


int Bit(ll x){
	if(!x)
		return 0;
	return 1+Bit(x>>1);
}


















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

using namespace std;

#define INF 1e9
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

ll N,K, min_v = 1, pref, suff;
vll A;

void solve(){

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

int main(){
    cin >> N >> K;
    A.resize(N,0);
    rep(i,N)
        cin >> A[i];

    solve();
}


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

def dec2n(int1, int2):
  l = ""
  while int1 != 0:
    l += str(int1 % int2)
    int1 = int1 // int2
  return l[::-1]

if K == 10:
  print(len(str(N)))
else:
  print(len(dec2n(N, K)))

Measured memory_bytes: 9068