akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647

int main() {
    int n, k; cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h.at(i);
    }
    vector<int> costs(n, INF);
    costs.at(0) = 0;
    for (int i = 0; i < n-1; i++) {
        int mx = min(i+k, n-1);
        for (int j = i; j <= mx; j++) {
            costs.at(j) = min(costs.at(j), costs.at(i) + abs(h.at(j) - h.at(i)));
        }
    }
    cout << costs.at(n-1) << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ld> vld;
typedef vector<string> vstr;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;  // 小さい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;     // 大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define endl "\n"

ll INF = 1e9;
ll MOD = 1000000007;
ll LINF = 1e18;
ld EPS = 1e-9;
ld PI = M_PI;
vll dx = {1, 0, -1, 0, 1, -1, -1, 1};
vll dy = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b;}     //最小公倍数

void yes(){ cout << "YES" << endl;}
void no(){ cout << "NO" << endl;}

//-----------------------------------------

//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  string s;
  cin >> s;
  ll k;
  cin >> k;

  ll i = 0;
  while(1){
    if(s[i] == '1'){
      k--;
      if(k == 0){
        cout << 1 << endl;
        return 0;
      }
    }
    else{
      cout << s[i] << endl;
      return 0;
    }
    i++;
  }





  return 0;
}



Measured memory_bytes: 3616
#include <iostream>

#include<vector>

#include<string>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#include<utility> 

#include<cstdio> 

#define vii vector< pair<int,int> >

#define vi vector<int>

#define INF 1000000007

#define ff first

#define ss second

#define lli long long int

#define ulli unsigned long long int

using namespace std;

int main() {

 ios_base::sync_with_stdio(false);

    cin.tie(NULL);

  string s;

  cin>>s;

  lli ans=0;

  for(int i=0; i<s.size(); i++){

    ans+=s[i]-'0';

  }

  if(ans%9==0)

  cout<<"Yes";

  else cout<<"No";

}

Measured memory_bytes: 3672
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

string ch_st_ll(ll t){
	string res;
	while(t > 0){
		res += (char)('0' + t % 2);
		t /= 2;
	}
	return res;
}

string fill_zero(string s, int len){
	stringstream ss;
	ss << setw(len) << setfill('0') << s;
	return ss.str();
}

int main(){
	ll N, K, input;
	cin >> N >> K;
	string stk = ch_st_ll(K);
	reverse(all(stk));
	int max_len = stk.size();
	vector<string> sta(N);
	rep(i,N){
		cin >> input;
		sta[i] = ch_st_ll(input);
		max_len = max(max_len, (int)sta[i].size());
		reverse(all(sta[i]));
	}
	stk = fill_zero(stk, max_len);
	rep(i,N)sta[i] = fill_zero(sta[i], max_len);

	//dp
	ll dp[50][2] = {0};
	rep(i,max_len)rep(k,2){
		int nd = stk[i] - '0';
		if(i == 0 && k == 1)continue;
		rep(d,2){
			int ni = i+1, nk = k;
			ll add = 0;
			if(k == 0){
				if(d > nd)continue;
				if(d < nd)nk = 1;
			}
			rep(ind, N){
				add += d ^ (sta[ind][i]-'0');
			}
			add *= pow(2, max_len-1-i);
			dp[ni][nk] = max(dp[ni][nk], dp[i][k] + add);
			//cout << line << endl;
			//printf("[digit, k, d, nd] -> [%d, %d, %d, %d]\n", i, k, d, nd);
			//printf("[add, nk] -> [%lld, %d]\n", add, nk);
			//REP(i,max_len)cout << dp[i][0] << ' '; cout << endl;
			//REP(i,max_len)cout << dp[i][1] << ' '; cout << endl;
			//cout << line << endl;
		}
	}
	cout << max(dp[max_len][0], dp[max_len][1]) << endl;
	return 0;
}


Measured memory_bytes: 14240
import java.util.Scanner;
 
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int a = 100;
for (int i = 0; i < n; i++) {
a = (int)Math.ceil(a * 1.05);
}
System.out.println(a * 1000);
}
}

Measured memory_bytes: 17300
#!/usr/bin/env python

def main():
    n = int(input())
    list_ = [[] for i in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            x -= 1
            list_[i].append((x, y))

    c_max = 0
    for i in range(2 ** n):
        cnt = 0
        for j in range(n):
            if (i >> j) & 1:
                cnt += 1
                for xy in list_[j]:
                    x, y = xy
                    if ((i >> x) ^ y) & 1:
                        break
                else:
                    continue
                break
        else:
            if cnt > c_max:
                c_max = cnt
            continue

    print(c_max)


if __name__ == '__main__':
    main()


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

int main()
{
    int n, l;
    cin >> n >> l;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    bool ok = false;
    int id = -1;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] + a[i + 1] >= l) {
            ok = true;
            id = i + 1;
            break;
        }
    }
    if (ok) {
        puts("Possible");
        //cout << "Id = " << id << "\n";
        for (int i = 1; i < id; i++) {
            cout << i << "\n";
        }
        for (int i = n - 1; i >= id; i--) {
            cout << i << "\n";
        }
    }
    else puts("Impossible");
}


Measured memory_bytes: 1152
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<functional>
#define For(i, N) for (i = 0; i < N; i++)
#define rep(N) for (int i = 0; i < N; i++)

using namespace std;
using ll = long long int;
using vi = vector<int>;

template<typename T>
void say(T s) {
	cout << s << endl;
}

int main() {
	string s;
	cin >> s;
	s[3] = '8';
	say(s);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, count = 0; cin >> N;
  for(int i = 1; i <= N; i++) if((i > 0 && i < 10) || (i >= 100 && i < 1000) || (i >= 10000 && i < 100000)) count++;
  cout << count << endl;
}

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

int main() {
	int a, b, c, d; cin >> a >> b >> c >> d;
	bool ok = false;
	while(true){
		c -= b;
		if(c <= 0){
			ok = true;
			break;
		}
		 a -= d;
		if(a <= 0) break;
	}
	if(ok) cout << "Yes" << endl;
	else cout << "No" << endl;
} 

Measured memory_bytes: 3628
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(" ", $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int)$this->next();
    }

    public function nextDouble()
    {
        return (double)$this->next();
    }
}

class out
{
    public static function printIn($str = "")
    {
        echo $str . PHP_EOL;
    }
}

$sc = new Scanner;

$s = $sc->next();
$t = $sc->next();

$s_arr = str_split($s);
$t_arr = str_split($t);
sort($s_arr);
rsort($t_arr);
$s = implode($s_arr);
$t = implode($t_arr);
$arr = [$s,$t];
sort($arr);
if($arr[0] == $arr[1]){
    echo 'No';
}
elseif ($arr[0] == $s){
    echo 'Yes';
}else {
    echo 'No';
}

Measured memory_bytes: 4856
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n, k = 0; cin >> n;
	k += n / 1000000000;
	k += n % 1000000000 / 100000000;
	k += n % 100000000 / 10000000;
	k += n % 10000000 / 1000000;
	k += n % 1000000 / 100000;
	k += n % 100000 / 10000;
	k += n % 10000 / 1000;
	k += n % 1000 / 100;
	k += n % 100 / 10;
	k += n % 10;
	if (n%k == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	cin >> n;
}

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

int main() {
   int N,L;
  cin>>N>>L;
  int sum=0;
  int answer=L;
  for(int i=1;i<N+1;i++){
    sum+=L+i-1;
  }
  for(int i=2;i<N+1;i++){
    if(abs(answer)>abs(L+i-1)){
      answer=L+i-1;
    }
  }
  int ans=sum-answer;
    cout<<ans<<endl;
}
  
    


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

const int N = 210;

int n, l[N];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= 2 * n; ++i) cin >> l[i];
	sort(l + 1, l + 2 * n + 1);

	int ans = 0;
	for (int i = 1; i <= 2 * n; i += 2) ans += l[i];
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  cin >> n >> k;
  int s=0;
  for(int i=0;i<n;i++){
    int x;
    cin >> x;
    if(2*x <= 2*(k-x)){
      s+=2*x;
    }else{
      s+=2*(k-x);
    }
  }
  cout << s << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;

ll gcd(ll a,ll b)
{
  if(a>b)swap(a,b);
  if(a==0){return b;}
  else return gcd(b%a,a);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a,b,c,d;cin>>a>>b>>c>>d;
  auto cal=[&](ll num){
    ll res=num;
    res-=num/c+num/d-num/(c/gcd(c,d)*d);
    return res;
  };
  cout<<cal(b)-cal(a-1)<<endl;
  return 0;

}


Measured memory_bytes: 256
def solve():
    N, M = map(int, input().split())
    L = [0 for _ in range(M)]
    R = [0 for _ in range(M)]
    for i in range(M):
        L[i], R[i] = map(int, input().split())
    
    ans = max(0, min(R) - max(L) + 1)
    print(ans)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 11016
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        s = s + sc.next();
        s= s + sc.next();
        int ans = Integer.parseInt(s);
        if(ans % 4 == 0) System.out.println("YES");
        else System.out.println("NO");
    }
}


Measured memory_bytes: 39348
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
	string a;
	cin >> a;
	if (a.size() >= 6) {
		bool hantei = false;
		bool hantei2 = false;
		bool hantei3 = false;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] >= '0' && a[i] <= '9') {
				hantei = true;
			} else if (isupper(a[i])) {
				hantei2 = true;
			} else if (islower(a[i])) {
				hantei3 = true;
			}
		}
		if (hantei && hantei2 && hantei3) {
			cout << "VALID" << endl;
		} else {
			cout << "INVALID" << endl;
		}
	} else {
		cout << "INVALID" << endl;
	}
	return 0;
}

Measured memory_bytes: 1180
N, x = map(int, input().split())
A = list(map(int, input().split()))
INF = float('inf')
cum = [[INF]*N for _ in range(N)]
for i in range(N):
  for j in range(i,N):
    cum[i][j] = min(cum[i][j-1],A[j])
ans = INF
for k in range(N):
  score = 0
  for j in range(N):
    if j-k>=0:
      score += cum[j-k][j]
    else:
      score += min(cum[0][j],cum[(j-k)%N][-1])
  ans = min(ans, k*x+score)
print(ans)

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

int main() {
	int a, b, c, n;
	cin >> a >> b >> c;
	if(a > b){
		n = b;
		b = a;
		a = n;
	}
	if(b > c){
		n = c;
		c = b;
		b = n;
	}
	if(a > b){
		n = b;
		b = a;
		a = n;
	}

	cout << a << " " << b << " " << c << endl;

	return 0;
}

Measured memory_bytes: 3068
#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,h,A;
    scanf("%d%d%d",&a,&b,&h);
    if(a==b && b==h)
    {
        A=a*a;
        printf("%d\n",A);

    }
    else
    {
        A=((a+b)*h)/2;
        printf("%d\n",A);

    }



return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(x,y) (x=min(x,y))
#define chmax(x,y) (x=max(x,y))
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define N 60
int a[N];
int main(){
	int n, m;
  cin>>n>>m;
  rep(i, m){
    int u, v;
    cin>>u>>v;
    a[u]++;
    a[v]++;
  }
  rep(i, n) cout<<a[i+1]<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	int n,m;
	cin>>n>>m;
	int a[m],b[m],c[m];
	set<pair<int,int>>edges[n][n];
	int dist[n][n];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++){
			if(i==j)
				dist[i][j]=0;
			else
				dist[i][j]=100000;
		}
	}
	for(int i=0;i<m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		a[i]--;
		b[i]--;
	}
	for(int i=0;i<m;i++)
	{
		dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);
		dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i]);
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=0;k<n;k++)
			{

				dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);

				}
			}
		}
	
		int ans=m;
		for(int i=0;i<m;i++)
		{
			bool inc=false;
			for(int j=0;j<n;j++)
			{
				if(dist[j][a[i]]+c[i]==dist[j][b[i]])
					inc=true;
			}
			if(inc==true)
				ans--;
		}

cout<<ans<<"\n";

}

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

int	main () {
  string S, T;
  cin >> S >> T;
  if (S.length() < T.length()) {
    cout << "UNRESTORABLE";
  }
  else {
    bool check_s, check_l = false;
    string U, ans;
    for (int i = 0; i < S.length() - T.length() + 1; i++) {
      check_s = true;
      for (int j = 0; j < T.length(); j++) {
        if (S[i+j] != '?' && S[i+j] != T[j]) {
          check_s = false;
        }
      }
      if (check_s) {
        check_l = true;
        U = S;
        for (int j = 0; j < T.length(); j++) {
          U[i+j] = T[j];
        }
        for (int j = 0; j < S.length(); j++) {
          if (U[j] == '?') {
            U[j] = 'a';
          }
        }
        ans = U;
      }
    }
    if (check_l) {
      cout << ans;
    }
    else {
      cout << "UNRESTORABLE";
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int n;
  cin >> n;
  
  int a = n % 10;
  int b = n % 100 / 10;
  int c = n % 1000 / 100;
  n = n / 1000;
  
  if ( b != c ) {
    cout << "No" << endl;
  }
  
  else if ( a == b || c == n)  {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;

string ans, s;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> s;
	for (auto i : s)
		if (i == '1')
			ans += '9';
		else if (i == '9')
			ans += '1';
		else
			ans += i;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
  ll a,b,i;
  cin>>a>>b;
  if(a<b)
  {
    for(i=0;i<b;i++)
    {
        cout<<a;
    }
    cout<<endl;
  }
  else
  {
      for(i=0;i<a;i++)
    {
        cout<<b;
    }
    cout<<endl;

  }
 return 0;
 }


Measured memory_bytes: 764
// -*- mode:c++; coding:utf-8; indent-tabs-mode:nil; -*-
// ALDS1_3-B: Queue

#include <cassert>
#include <cstdio>

template <typename T>
class queue {
  unsigned int head_ = 0U; // C++11
  unsigned int size_ = 0U;
  const unsigned int max_;
  T* dp_;
public:
  queue(unsigned int max) : max_(max) { dp_ = new T[max]; }
  ~queue() { delete[] dp_; }
  void enqueue(T d) {
    assert(!is_full());
    const unsigned int tail = mod_by_max(head_+size_);
    dp_[tail] = d;
    ++size_;
  }
  T dequeue() {
    assert(!is_empty());
    T d = dp_[head_];
    head_ = mod_by_max(head_+1);
    --size_;
    return d;
  }
  inline bool is_empty() const { return size_ == 0; }
  inline bool is_full() const { return size_ == max_; }
private:
  inline int mod_by_max(unsigned int i) const { return i < max_ ? i : i -max_; }
};

struct process {
  char name_[10+1];
  unsigned int time_;
  inline unsigned int exec(unsigned int quantum) {
    const unsigned int elapse = time_ > quantum ? quantum : time_;
    time_ -= elapse;
    return elapse;
  }
  inline bool is_finished() const { return time_ == 0; }
};

int main(void) {
  unsigned int n, q;
  std::scanf("%d %d", &n, &q);

  process processes[n];
  queue<process*> process_queue(n);
  for (auto i = 0U; i < n; ++i) {
    std::scanf("%10s %d", processes[i].name_, &processes[i].time_);
    process_queue.enqueue(&processes[i]);
  }

  const unsigned int quantum = q;
  unsigned int elapse = 0;
  while (!process_queue.is_empty()) {
    process* current_process = process_queue.dequeue();
    elapse += current_process->exec(quantum);
    if (current_process->is_finished()) {
      printf("%s %d\n", current_process->name_, elapse);
    } else {
      process_queue.enqueue(current_process);
    }
  }

  return 0;
}
// end

Measured memory_bytes: 3348
from collections import deque
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
d = deque([0]*k)
popleft = d.popleft
append = d.append
result = 0
temp = ""
for el in t:
    if el == "r":
        if popleft() != "p":
            result += p
            append("p")
        else:
            append("n")
    elif el == "s":
        if popleft() != "r":
            result += r
            append("r")
        else:
            append("n")
    else:
        if popleft() != "s":
            result += s
            append("s")
        else:
            append("n")
print(result)

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

int main() {
  int N; cin >> N;
  vector<vector<int>> x(N);
  vector<vector<int>> y(N);
  for (int i =0; i<N; i++) {
    int a; cin >> a;
    for (int j =0; j<a; j++) {
      int b,c; cin >> b >> c;
      x.at(i).push_back(b);
      y.at(i).push_back(c);
    }
  }
  
  int count =0; bool check = true;
  for (int tmp =0; tmp< 1 << 15; tmp++) {
    if (tmp >= (1 << N)) continue;
    bitset<15> s(tmp);
    for (int i =0; i<N; i++) {
      if (s[i] == 0) continue;
      int a = x.at(i).size();
      for (int j =0; j<a; j++) {
        if (s[x.at(i).at(j) - 1] != y.at(i).at(j)) {
          check = false;
          break;
        }
      }
    }
    int count1 = s.count();
    if(check) count = max(count1,count);
    check = true;
  }
  cout << count << endl; 
}

Measured memory_bytes: 3548
/*
ID: barish21
LANG: C++14
TASK: test
*/

/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();

const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;

const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;

const intt INF = 2LL * 1000000000;
/***************/

/***Additional Functions***/

intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

intt gcd (intt a, intt b) {
    while (b > 0) {
        intt t = a % b;
        a = b, b = t;
    }
    return a;
}

intt lcm (intt a, intt b) {
    return (a / gcd (a, b)) * b;
}

intt is_prime (intt n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (intt i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/**************************/

intt n, q;
intt par[maxx];

void init () {
    memset (par, -1, sizeof (par));
}

intt Find (intt x) {
    return (par[x] < 0 ? x : Find (par[x]));
}

void Union (intt x, intt y) {
    x = Find (x), y = Find (y);
    if (x == y)
        return;
    if (par[x] > par[y])
        swap (x, y);
    par[x] += par[y];
    par[y] = x;
}

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    IO;
    init ();
    cin >> n >> q;
    while (q --) {
        intt type, x, y;
        cin >> type >> x >> y;
        if (type == 0)
            Union (x, y);
        else
            cout << (Find (x) == Find (y)) << endl;
    }
    return 0;
}

Measured memory_bytes: 4008
# 二分探索
from bisect import bisect_left

INF = float('inf')

def f(x, s, t):
    result = INF
    i = bisect_left(s, x)
    if i > 0:
        j = bisect_left(t, s[i - 1])
        if j > 0:
            result = min(result, (x - s[i - 1]) + (s[i - 1] - t[j - 1]))
        if j < len(t):
            result = min(result, (x - s[i - 1]) + (t[j] - s[i - 1]))
    if i < len(s):
        j = bisect_left(t, s[i])
        if j > 0:
            result = min(result, (s[i] - x) + (s[i] - t[j - 1]))
        if j < len(t):
            result = min(result, (s[i] - x) + (t[j] - s[i]))
    return result


A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]

for i in range(Q):
    x = int(input())
    print(min(f(x, s, t), f(x, t, s)))


Measured memory_bytes: 12092
#include <stdio.h>

int main(void)
{
   int a,b;
   scanf("%d %d",&a,&b);
   if(a<b){
   	 printf("a < b\n");
   }
    if(a>b){
   	 printf("a > b\n");
    }
    if(a==b){
   	printf("a == b\n");
   }
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
const double PI = acos(-1);
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x) {
        if(par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool issame(int x, int y) { return root(x) == root(y); }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y)
            return false;
        if(par[x] > par[y])
            swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) { return -par[root(x)]; }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    int ans = 0;
    for(int i = 0; i < m; i++) {
        UnionFind uf(n);
        for(int j = 0; j < m; j++) {
            if(i == j) {
                continue;
            }
            uf.merge(a[j], b[j]);
        }
        set<int> se;
        for(int i = 0; i < n; i++) {
            se.insert(uf.root(i));
        }
        if(se.size() > 1) {
            ans++;
        }
    }
    cout << ans << endl;
}

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

#define LL long long

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	LL n,m;
	cin >> n >> m;
	vector<LL> a(n);
	for (LL i = 0; i < n; i++)
		cin >> a[i];
	priority_queue<LL> pq;
	for (LL i = 0; i < n; i++){
		pq.push(a[i]);
	}
	for (LL i = 0; i < m; i++){
		LL x = pq.top();
		pq.pop();
		pq.push(x/2);
	}
	LL res = 0;
	while (!pq.empty()){
		res += pq.top();
		pq.pop();
	}
	cout << res << "\n";
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pd(n) printf("%d",n)
#define pl(n) printf("%lld",n)
#define endc printf("\n")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int maxn = 2e5 + 7; 
//const int md = 1e9 + 7;

ll a[maxn];

int main() {
	// IOS;
	int n; sd(n);
	for (int i = 1; i <= n; i++) {
		sl(a[i]);
	}
	sort(a+1,a+n+1);
	ll mx = 0, mx2 = 0;
	for (int i = n; i >= 2; i--) {
		if (a[i] == a[i-1]) {
			if (mx <= 0) { mx = a[i]; i--; }
			else if (mx2 <= 0) { mx2 = a[i]; i--; }
		}
	}
	pl(mx*mx2); endc;
}


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

int main(){
  int n,i,p,ans=0,l=0;
  cin >> n;
  for(i=0; i<n; i++){
    cin >> p;
    ans+=p;
    l=max(l,p);
  }
  cout << ans-l/2;
}
  

Measured memory_bytes: 256
import math
a,b,x = map(int,input().split())
ok = 0.0
ng = 90.0
z = math.degrees(math.atan2(b,a))

def f(y):
    if y >= z:
        return b*b*a/(math.tan(math.radians(y))*2.0)
    else:
        return a*a*b-a*a*a*math.tan(math.radians(y))/2.0


for _ in [0]*1000:
    mid = (ok+ng)/2
    if f(mid) >= x:
        ok = mid
    else:
        ng = mid

print(ok)



Measured memory_bytes: 38384
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b, w = lr()
    graph[a].append((b, w%2))
    graph[b].append((a, w%2))

color = [None] * (N+1)
color[1] = 0
root = 1
parent = [0] * (N+1)
stack = [(root, 0)]
while stack:
    cur, c = stack.pop()
    for next, weight in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        if weight == 0:
            color[next] = c
        else:
            color[next] = 1 - c
        stack.append((next, color[next]))

print(*color[1:], sep='\n')


Measured memory_bytes: 41796
#include<iostream>
#include<string>

using namespace std;

string replaceAll(string &replacedStr, string from, string to){
    unsigned int pos = replacedStr.find(from);
    int toLen = to.length();

    if(from.empty()){
        return replacedStr;
    }

    while((replacedStr.find(from,pos)) != string::npos){
        pos = replacedStr.find(from,pos);
        replacedStr.replace(pos,from.length(),to);
        pos += toLen;
    }
    return replacedStr;
}

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        string a;
        cin >> a;
        for(int k=0;k<10;k++){
            replaceAll(a,"111111","1");
            replaceAll(a,"2222","2");
            replaceAll(a,"3333","3");
            replaceAll(a,"4444","4");
            replaceAll(a,"5555","5");
            replaceAll(a,"6666","6");
            replaceAll(a,"77777","7");
            replaceAll(a,"8888","8");
            replaceAll(a,"99999","9");
        }
        replaceAll(a,"111110"," ");
        replaceAll(a,"11110","?");
        replaceAll(a,"1110","!");
        replaceAll(a,"110",",");
        replaceAll(a,"10",".");
        replaceAll(a,"2220","c");
        replaceAll(a,"220","b");
        replaceAll(a,"20","a");
        replaceAll(a,"3330","f");
        replaceAll(a,"330","e");
        replaceAll(a,"30","d");
        replaceAll(a,"4440","i");
        replaceAll(a,"440","h");
        replaceAll(a,"40","g");
        replaceAll(a,"5550","l");
        replaceAll(a,"550","k");
        replaceAll(a,"50","j");
        replaceAll(a,"6660","o");
        replaceAll(a,"660","n");
        replaceAll(a,"60","m");
        replaceAll(a,"77770","s");
        replaceAll(a,"7770","r");
        replaceAll(a,"770","q");
        replaceAll(a,"70","p");
        replaceAll(a,"8880","v");
        replaceAll(a,"880","u");
        replaceAll(a,"80","t");
        replaceAll(a,"99990","z");
        replaceAll(a,"9990","y");
        replaceAll(a,"990","x");
        replaceAll(a,"90","w");
        replaceAll(a,"0","");
        cout << a << endl;
    }
}


Measured memory_bytes: 3200
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;



int main(){
    int n, m, q;
    int a[55], b[55], c[55], d[55];
    cin >> n >> m >> q;
    for(int i = 0;i < q;i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    vector<int> vec(n+m-1, 1);
    for(int i = 0;i < m-1;i++)vec[i] = 0;
    int ans = 0;
    do{
        int zero_cnt = 0;
        int score = 0;
        vector<int> A;
        for(int i = 0;i < n+m;i++){
            if(vec[i] == 0)zero_cnt++;
            else A.push_back(zero_cnt + 1);
        }
        for(int i = 0;i < q;i++){
            if(A[b[i]] - A[a[i]] == c[i])score += d[i];
        }
        ans = max(ans, score);
    }while(next_permutation(vec.begin(), vec.end()));

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

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

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1; finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int n;
  cin>>n;
  int x[n];
  for (int i=0; i<n; i++) cin>>x[i];
  COMinit();
  long long ans = 0;
  long long p = 1;
  for (int i=1; i<n; i++) {
    ans += p * (x[i] - x[i-1]) % MOD;
    ans %= MOD;
    p += inv[i+1];
    p %= MOD;
  }
  ans *= fac[n-1];
  ans %= MOD;
  cout<<ans<<endl;
}

Measured memory_bytes: 12544
N, x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0

for i, v in enumerate(a):
    x -= v
    if x < 0:
        ans = i
        break
    if x == 0:
        ans = i + 1
        break
    if i == N - 1: 
        ans = i + 1
if x > 0:
    ans -= 1
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
int main(void)
{
	int x,y,flg,t,k,i;
	scanf("%d %d",&x,&y);
	flg=0;
	for(i=0;i<=x;i++){
		t=i;
		k=x-i;
		if(t*2+k*4==y){
			flg=1;
		}
	}
	if(flg==1){
			printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}
			

Measured memory_bytes: 1608
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a+b==15)
	    printf("+");
	else if(a*b==15)
	    printf("*");
	else if(a+b!=15&&a*b!=15)
	    printf("x");
	return 0;		 
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('\n')
template <typename qwq> inline void read(qwq &x)
{
	x = 0;
	rg int f = 1;
	rg char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	x *= f;
}
template <typename qaq> inline void print(qaq x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');	
}
const int maxn = 2333;
int n, m, a, b, tmpb, tmpa, flag;
int Map[maxn][maxn];
int col[maxn];
int main()
{
	read(n), read(m), read(a), read(b);
	tmpb = b, tmpa = a;
	begin:
	for (rg int i = 1; i <= n; ++i)
	{
		rg int tot = 0;
		for (rg int j = 1; j <= m; ++j)
		{
			if (col[j] < b) Map[i][j] = 1, ++tot, ++col[j];
			if (tot == a) break; 
		}
		if (tot != a && tot != m - a)
		{
			++flag;
			break;
		}
		if (i == n)
		{
			rg bool isOk = true;
			for (rg int j = 1; j <= m; ++j)
			{
				if (col[j] != b && col[j] != n - b)
				{
					isOk = false;
					++flag;
					break;
				}
			}
			if (isOk) flag = 0;
		}
	}
	if (flag)
	{
		if (flag == 1) b = n - tmpb, a = tmpa;
		if (flag == 2) b = tmpb, a = m - tmpa;
		if (flag == 3) b = n - tmpb, a = m - tmpa;
		if (flag == 4)
		{
			print(-1);
			return 0;
		}
		for (rg int i = 1; i <= n; ++i)
		{
			for (rg int j = 1; j <= m; ++j)
			{
				col[j] = 0;
				Map[i][j] = 0;
			}
		}
		goto begin;
	}
	for (rg int i = 1; i <= n; ++i)
	{
		for (rg int j = 1; j <= m; ++j)
		{
			print(Map[i][j]);
		}
		__endl;
	}
	return 0;
}

Measured memory_bytes: 11136
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Point {
public:
	long double px, py;
	Point() : px(0), py(0) {};
	Point(long double px_, long double py_) : px(px_), py(py_) {};
	bool operator==(const Point& p) const { return px == p.px && py == p.py; }
	bool operator!=(const Point& p) const { return px != p.px || py != p.py; }
	bool operator<(const Point& p) const { return px < p.px ? true : (px == p.px && py < p.py); }
	bool operator>(const Point& p) const { return px > p.px ? true : (px == p.px && py > p.py); }
	bool operator<=(const Point& p) const { return !(Point(px, py) > p); }
	bool operator>=(const Point& p) const { return !(Point(px, py) < p); }
	Point operator+(const Point& p) const { return Point(px + p.px, py + p.py); }
	Point operator-(const Point& p) const { return Point(px - p.px, py - p.py); }
	Point operator/(long double d) const { return Point(px / d, py / d); }
	friend Point operator*(const Point p, long double d) { return Point(p.px * d, p.py * d); }
	friend Point operator*(long double d, const Point& p) { return p * d; }
	Point& operator+=(const Point& p1) { px += p1.px, py += p1.py; return *this; }
	Point& operator-=(const Point& p1) { px -= p1.px, py -= p1.py; return *this; }
	Point& operator*=(long double d) { px *= d, py *= d; return *this; }
	Point& operator/=(long double d) { px /= d, py /= d; return *this; }
};
class Segment {
public:
	Point p1, p2;
	Segment() : p1(Point()), p2(Point()) {};
	Segment(Point p1_, Point p2_) : p1(p1_), p2(p2_) {};
	Segment(long double p1x, long double p1y, long double p2x, long double p2y) : p1(Point(p1x, p1y)), p2(Point(p2x, p2y)) {};
	bool operator==(const Segment& s) const { return (p1 == s.p1 && p2 == s.p2) || (p1 == s.p2 && p2 == s.p1); }
	bool operator!=(const Segment& s) const { return !(Segment(p1, p2) == s); }
};
long double norm(const Point& a) { return a.px * a.px + a.py * a.py; }
long double abs(const Point& a) { return sqrtl(norm(a)); }
long double arg(const Point& a) { return atan2l(a.py, a.px); }
long double dot(const Point& a, const Point& b) { return a.px * b.px + a.py * b.py; }
long double crs(const Point& a, const Point& b) { return a.px * b.py - a.py * b.px; }
long double dst(const Point& a, const Point& b) { return abs(b - a); }
long double dst(const Segment& a, const Point& b) { return dot(a.p2 - a.p1, b - a.p1) < 0.0 ? abs(b - a.p1) : (dot(a.p1 - a.p2, b - a.p2) < 0.0 ? abs(b - a.p2) : abs(crs(a.p2 - a.p1, b - a.p1) / abs(a.p2 - a.p1))); }
int n, q, r[109]; Point c[109], s, t;
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> c[i].px >> c[i].py >> r[i];
		}
		cin >> q;
		while(q--) {
			cin >> s.px >> s.py >> t.px >> t.py;
			bool flag = false;
			for (int i = 0; i < n; i++) {
				long double z1 = dst(s, c[i]), z2 = dst(t, c[i]);
				long double z3 = dst(Segment(s, t), c[i]);
				bool f1 = (z1 > r[i]), f2 = (z2 > r[i]);
				if (f1 != f2) flag = true;
				if (f1 && f2 && z3 <= r[i]) flag = true;
			}
			cout << (flag ? "Safe" : "Danger") << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3180
M = "afkpuzbglqv.chmrw?dinsx!ejoty "
while True:
    try:
        s = raw_input()
        l = len(s)
        mes = ""
        if l&1:
            1/0
        for i in xrange(l/2):
            i1 = int(s[2*i])-1; i2 = int(s[2*i+1])-1
            if 0<=i1<=5 and 0<=i2<=4:
                mes += M[i1 + i2*6]
            else:
                1/0
        print mes
    except EOFError:
        break
    except Exception:
        print "NA"
        continue

Measured memory_bytes: 4220
n, k = map(int, input().split())
an = [int(num) for num in input().split()]

kind = {}
for a in an:
  if not a in kind:
    kind[a] = 1
  else :
    kind[a] += 1

sortedKind = sorted(kind.items(), key=lambda x:x[1])    

if len(sortedKind) > k:
  count = 0
  for check in sortedKind[:len(sortedKind)-k]:
    count += check[1]
  print(count)
else :
  print(0)


Measured memory_bytes: 42848
#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define kill _z_kill
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outv(x) cerr<<#x" = "<<x<<"  "
#define outtag(x) cerr<<"--------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
	For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
#define User_Time ((double)clock()/CLOCKS_PER_SEC)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned uint;
typedef long double LD;
typedef vector <int> vi;
typedef pair <int,int> pii;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
//int Pow(int x,int y){
//	int ans=1;
//	for (;y;y>>=1,x=(LL)x*x%mod)
//		if (y&1)
//			ans=(LL)ans*x%mod;
//	return ans;
//}
//void Add(int &x,int y){
//	if ((x+=y)>=mod)
//		x-=mod;
//}
//void Del(int &x,int y){
//	if ((x-=y)<0)
//		x+=mod;
//}
//int Add(int x){
//	return x>=mod?x-mod:x;
//}
//int Del(int x){
//	return x<0?x+mod:x;
//}
void ckmax(int &x,int y){
	if (x<y)
		x=y;
}
void ckmin(int &x,int y){
	if (x>y)
		x=y;
}
const int N=200005,INF=1.05e9;
int n,t;
pii a[N];
bool cmp(pii a,pii b){
	LL ta=(LL)b.fi*a.se+b.se,tb=(LL)a.fi*b.se+a.se;
	if (ta!=tb)
		return ta<tb;
	return a.se<b.se;
}
int dp[N][31];
int main(){
	n=read(),t=read();
	For(i,1,n){
		a[i].fi=read();
		a[i].se=read()+a[i].fi+1;
		a[i].fi++;
	}
	sort(a+1,a+n+1,cmp);
	int m=n;
	while (m>0&&a[m].fi==1)
		m--;
	For(i,0,m)
		For(j,0,30)
			dp[i][j]=INF;
	dp[0][0]=0;
	For(i,1,m)
		For(j,0,30){
			int v=dp[i-1][j];
			if (v>=INF)
				continue;
			ckmin(dp[i][j],v);
			if (j<30)
				dp[i][j+1]=min((LL)dp[i][j+1],(LL)a[i].fi*v+a[i].se);
		}
	int ans=0;
	For(i,0,30){
		int now=dp[m][i];
		if (now>t)
			continue;
		int tmp=i;
		For(j,m+1,n){
			now+=a[j].se;
			if (now>t)
				break;
			tmp++;
		}
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 25984
a,b,m = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = list(map(int,input().split()))
xyc = [list(map(int,input().split())) for _ in range(m)]
a_min = min(a_list)
b_min = min(b_list)
s = a_min + b_min
for i in range(m):
    x,y,c = xyc[i][0]-1,xyc[i][1]-1,xyc[i][2]
    s = min(s, a_list[x]+b_list[y]-c)
print(s)

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    string ans = "APPROVED";
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    for(int i=0; i<n; i++){
        if(a[i]%2==0){
            if(a[i]%3!=0 && a[i]%5!=0){
                ans = "DENIED";
                break;
            }
        }
    }

    cout << ans << endl;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 1000010
#define rep(i,n) for (int i = 0; i < (n); ++i)
const ll mod = 1e9+7;

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

int memo[MAXN];
int N;

int f(int i) {
    int res = 10000000;

    if (i==0) return 0;
    if (memo[i]) return memo[i];

    //1 yen

    chmin(res, f(i-1) + 1); 

    //6 yen

    int x=6;

    while(x<=i) {
        chmin(res, f(i-x)+1);
        x *= 6;
    }

    //9 yen

    x = 9;

    while(x<=i) {
        chmin(res, f(i-x)+1);
        x *= 9;
    }

    return memo[i] = res;
}

int main() {
    cin >> N;
    cout << f(N) << endl;

}



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

int main() {
  double n;
  cin >> n;
  double cnt = 0.0;
  for(int i = 1; i <= n; i++) {
    if(i % 2 != 0) cnt++;
  }
  
  double ans = cnt / n;
  printf("%.7f\n", ans);
}

Measured memory_bytes: 3736
/*
R         R R R R        R        R R R      R      R    R    R      R    R R R R                                                     
R         R             R R       R    RR    R R    R    R    R R    R    R              
R         R            R   R      R R R      R  R   R    R    R  R   R    R   R R                 
R         R R R       R R R R     R R        R   R  R    R    R   R  R    R     R                       
R         R          R       R    R   RR     R    R R    R    R    R R    R     R           
R R R R   R R R R   R         R   R     RR   R      R    R    R      R    R R R R               

*/


#include<bits/stdc++.h>
using namespace std;
#define  bf            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define  ll            long long
#define  pb            push_back
#define  pr            10
#define  mx            100000 // 10^6
#define  md            1000000007
#define  result(a)     cout<<a<<endl;
#define  forr(a,x)     for(int i=a;i<=x;i++)
#define  input(n,a)    int a[n];for(int i=0;i<n;i++)cin>>a[i];
#define  print(a)      for(auto it:a)cout<<it<<' '; //0-based 
#define  printt(n,a)   for(i=0;i<n;i++)cout<<a[i]<<' '; //1-based 
#define  sz(a)         cout<<a.size()<<endl; 
#define  prefx(n,a)    for(i=1;i<n;i++)a[i]=a[i-1]+a[i]; //0-based
#define  sortt(v)      sort(v.begin(),v.end());
#define  srt(n,a)      sort(a,a+n);
#define  rev(n,a)      reverse(a,a+n);
#define  revr(a)       reverse(a.begin(),a.end());
#define  yes           cout<<"yes\n";
#define  no            cout<<"no\n";

int main()
{
  ll n,i;
  cin>>n;
  input(n,a);
  sort(a,a+n);
  cout<<(a[n-1]-a[0])<<endl;
}

Measured memory_bytes: 3628
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define bp __builtin_popcountll
const int N = 5005;

int main()
{
    ll n,k;
    cin >> n >> k;
    ld sum = 0;
    ll a[n];
    for(ll i=0;i<n;i++)   cin >> a[i];
    for(ll i=0;i<k;i++)
    {
        ll temp = (a[i]*(a[i]+1))/2;
        sum += (temp/(ld)a[i]);
    }
    ld maxi = 0;
    maxi = sum;
    for(ll i=k;i<n;i++)
    {
        ll temp = (a[i]*(a[i]+1))/2;
        sum += (temp/(ld)a[i]);
        temp = (a[i-k]*(a[i-k]+1))/2;
        sum -= (temp/(ld)a[i-k]);
        maxi = max(maxi,sum);
    }
    cout<<setprecision(12)<<maxi;
    
}

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

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

    vector<pair<int,int>> a(n);
    vector<int> b(n);
    vector<pair<int,pair<int, int>>> c(n);
    for(int i=0; i<n; i++){
        cin >> a[i].first; 
        a[i].second = i;
    }
    for(int i=0; i<n; i++){
        cin >> b[i];
        c[i] = {b[i], a[i]};
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    
    vector<int> order(n);
    for(int i=0; i<n; i++){
        if(a[i].first > b[i]){
            cout << "No" << endl;
            return 0;
        }
        order[a[i].second] = i;
        
    }

    vector<int> cycle(n);
    int x = 1;
    for(int i=0; i<n; i++){
        int ni = c[i].second.second;
        if(cycle[ni] != 0) continue;

        while(cycle[ni] == 0){
            //cout << ni << " ";
            cycle[ni] = x;
            ni = c[order[ni]].second.second;
        }
        //cout << endl;
        x += 1;
    }
    //for(int i=0; i<n; i++) cout << cycle[i] << " ";
    //cout << endl;

    if(x >= 3){
        cout << "Yes" << endl;
        return 0;
    }

    for(int i=0; i<n-2; i++){
        if(b[i] >= a[i+1].first){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 6436
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
typedef long long ll;
typedef pair<int, int> P;
typedef struct{
  int first;
  int second;
  int third;
}T;

//昇順
bool comp_Se(T& l, T& r){
  return l.second < r.second;
}

int main(void){
  int N,T;
  cin >> N >> T;
  vector<P> v(N);
  int i;
  REP(i,N) cin >> v[i].first >> v[i].second;
  sort(v.begin(),v.end());
  REP(i,N){
    if(v[i].second <= T){
      cout << v[i].first << endl;
      break;
    }
  }
  if(i==N) cout << "TLE" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string st;
int sum1,sum2;
int main()
{
    cin>>st;
    sum1=2147483647;
    for(int i=0;i<st.size();i++)
        if(st[i]=='C' && sum1==2147483647)
            sum1=i;
        else
        if(st[i]=='F')
            sum2=i;
    if(sum1<sum2)
        cout<<"Yes";
        else cout<<"No";
    return 0;
}

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

int main()
{
    char str[8];
    int n,num[8];
    int big[8],small[8],diff[8];
    cin>>n;
    while(n--){
        cin>>str;
        for(int j=0;j<8;j++){
            num[j]=(int)str[j]-48;
        }
        sort(num,&num[8]);
        for(int j=0;j<8;j++){
            big[-(j-7)]=num[j];
            small[j]=num[j];
        }
        for(int j=7;j>=0;j--){
            if(big[j]<small[j]){
                big[j] += 10;
                big[j-1]--;
            }
            diff[j]=big[j]-small[j];
        }
        bool flag=false;
        for(int j=0;j<8;j++){
            if(diff[j]!=0 || j==7){
                cout<<diff[j];
                flag=true;
            }
            else if(flag){
                cout<<diff[j];
            }
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 1180