akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#define ll long long
#define ull unsigned long long
#define mod 1000000007

using namespace std;

int n, k, r, s, p;
ll dp[100005];
string t;

/*
	0 -> r
	1 -> s
	2 -> p
*/

/*ll solve(int pos, string S)
{
	if (pos == t.size()) return 0;
	if (dp[pos] != -1) return dp[pos];
	ll ans = 0;
	for (int i = 0; i < 3; i++)
	{
		if (pos <= k)
		{
			S.push_back(i + '0');
			if (t[pos] == 'r' && i == 2) ans = max(ans, p + solve(pos + 1, S));
			else if (t[pos] == 's' && i == 0) ans = max(ans, r + solve(pos + 1, S));
			else if (t[pos] == 'p' && i == 1)ans = max(ans, s + solve(pos + 1, S));
			else ans = max(ans, solve(pos + 1, S));
			S.pop_back();
		}
		else
		{
			if (S[pos - k] - '0' != i)
			{
				S.push_back(i + '0');
				if (t[pos] == 'r' && i == 2) ans = max(ans, p + solve(pos + 1, S));
				else if (t[pos] == 's' && i == 0) ans = max(ans, r + solve(pos + 1, S));
				else if (t[pos] == 'p' && i == 1)ans = max(ans, s + solve(pos + 1, S));
				else ans = max(ans, solve(pos + 1, S));
				S.pop_back();
			}
		}
	}
	return dp[pos] = ans;
}*/

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof dp);
	cin >> n >> k >> r >> s >> p >> t;
	//t = '*' + t;
	//cout << solve(1, "*") << '\n';
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (i < k || t[i] != t[i - k])
		{
			if (t[i] == 'r')
			{
				ans += p;
			}
			else if (t[i] == 's')
			{
				ans += r;
			}
			else
			{
				ans += s;
			}
		}
		else t[i] = 'z';
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 1280
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Main{

	//static long[] a;
	static	int N ;
	static	int M ;
	static int[][] dp;

	static	boolean[] flag ;

	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);			//文字の入力
		N = scanner.nextInt();
		M = scanner.nextInt();

		String s = scanner.next();
		String t = scanner.next();

		int gcd = gcd(N, M);
		long ans = (long)N/gcd*M;

		for(int i = 0;i < N;i += N/gcd(N, M) ){
			int x = (int)((long)M*i/N);
			if(s.charAt(i) != t.charAt(x)){
				System.out.println("-1");
				return;
			}
		}
		

		System.out.println(ans);


	}





//	static long lcm(long m, long n) {
//		return m * n / gcd(m, n);
//	}
	static int gcd(int a, int b){
		if (a<b){	//a>=bほしょー
			int c = a;	a = b;	b = c;
		}
		while(a%b!=0) {
			int c = a%b;	a=b;	b=c;
		}
		return b;
	}
 
}




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

int main() {
    //入力
    int a, b, c, d;
    char op1, op2, op3;
    string input;
    cin >> input;
    a = input[0] - '0'; 
    b = input[1] - '0'; 
    c = input[2] - '0';
    d = input[3] - '0';
    for (int bit = 0; bit < (1<<3); bit++) {
        int ans = a;
        if (bit & (1<<2)) {
            op1 = '+';
            ans += b;
        }
        else {
            op1 = '-';
            ans -= b;
        }

        if (bit & (1<<1)) {
            op2 = '+';
            ans += c;
        }
        else {
            op2 = '-';
            ans -= c;
        }

        if (bit & 1) {
            op3 = '+';
            ans += d;
        }
        else {
            op3 = '-';
            ans -= d;
        }
        
        if (ans == 7) break;
    }
    cout << a << op1 << b << op2 << c << op3 << d << "=7" << endl;
    return 0;
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int A[1];
int size=1;
int m=2;
#define N 101
#define mod 1000000007
#define f(i,n) for(int i=0;i<n;i++)

int main()
{
    fast;
    /*string str1,str2;
    cin>>str1>>str2;
    cout<<LCS(str1,str2,str1.size(),str2.size());*/
    int n;
    cin>>n;
    while(n>0)
    {   if(n%10==7)
        {cout<<"Yes\n";return 0;}
        n/=10;}
    cout<<"No\n";



}

Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

bool reach_fm_goal[512];
bool reach_fm_start[512];

int main() {
	int mx;
	while(cin >> mx, mx) {
		int n;
		vector<int> d;
		for(int i = 0; i < 512; i++)
			reach_fm_goal[i] = reach_fm_start[i] = false;
		cin >> n;
		d.resize(n+2);
		d[0] = d[n+1] = 0;
		for(int i = 0; i < n; i++)
			cin >> d[i+1];

		vector<vector<int> > edge, rev_edge;
		edge.resize((n+2)*2);
		rev_edge.resize((n+2)*2);
		for(int i = 0; i < n+2; i++) {
			for(int j = 0; j < min(mx, n+1 - i); j++) {
				edge[n+2 + i].push_back(i + j+1);
				rev_edge[i + j+1].push_back(n+2 + i);
			}
			if(d[i] > 0) {
				edge[i].push_back(n+2 + min(i+d[i], n+1));
				rev_edge[n+2 + min(i+d[i], n+1)].push_back(i);
			}
			else {
				edge[i].push_back(n+2 + max(i+d[i], 0));
				rev_edge[n+2 + max(i+d[i], 0)].push_back(i);
			}
		}

		/*
		for(int i = 0; i < rev_edge.size(); i++) {
			for(int j = 0; j < rev_edge[i].size(); j++) {
				cout << rev_edge[i][j] << " ";
			}
			cout << endl;
		}
		// */

		queue<int> q;
		q.push(0);
		reach_fm_start[0] = true;
		while(!q.empty()) {
			int cur = q.front();
			q.pop();
			for(int i = 0; i < edge[cur].size(); i++) {
				if(!reach_fm_start[edge[cur][i]]) {
					reach_fm_start[edge[cur][i]] = true;
					q.push(edge[cur][i]);
				}
			}
		}
		q.push((n+2)*2 - 1);
		reach_fm_goal[(n+2)*2 - 1] = true;
		while(!q.empty()) {
			int cur = q.front();
			q.pop();
			for(int i = 0; i < rev_edge[cur].size(); i++) {
				if(!reach_fm_goal[rev_edge[cur][i]]) {
					reach_fm_goal[rev_edge[cur][i]] = true;
					q.push(rev_edge[cur][i]);
				}
			}
		}
		bool flg = true;
		for(int i = 0; i < 512; i++) {
			if(reach_fm_start[i] && !reach_fm_goal[i])
				flg = false;
		}

		/*
		for(int i = 0; i < 20; i++) {
			cout << reach_fm_start[i] << " " << reach_fm_goal[i] << endl;
		}
		// */
		
		cout << (flg ? "OK" : "NG") << endl;
	}
}

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

int main() {
  ll x;
  cin >> x;
  for (long long i = -200; i <= 200; i++) {
    for (long long j = -200; j <= 200; j++) {
      ll a = i * i * i * i * i;
      ll b = j * j * j * j * j;
      if (a - b == x) {
        cout << i << " " << j << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 3620
#pragma region
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define all(x) x.begin(),x.end()
#pragma endregion


int main()
{
	int n; cin >> n;
	int res = 0;
	vector<int> a(n); rep(i, n)cin >> a[i];
	rep(i, n - 1)
	{
		int cnt = 1;
		while (i < n - 1 && a[i] == a[i + 1])
		{
			++cnt;
			++i;
		}
		res += cnt / 2;
	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<math.h>
#include<utility>
using namespace std;

int main(){
    int h, w;

    while(true){
        cin >> h >> w;
        if(h == 0 && w == 0) {
            //cout << endl;
            break;
        }

        for(int y=0;y<h;y++){
            for(int x=0;x<w;x++){
                if(y == 0 || y == h-1 || x == 0 || x == w-1) cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3084
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17

n, m = map(int, input().split())
ans = n * (n - 1) // 2 + m * (m - 1) // 2
print(ans)


Measured memory_bytes: 38256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int X,A;
	cin>>X>>A;
	cout<<(X<A?0:10)<<endl;
}

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

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

signed main(){
    int Q;
    cin>>Q;
    while(Q--){
        int c,a,n;
        cin>>c>>a>>n;

        int ans=0;
        int t=min(min(a,c),n);
        ans+=t;
        c-=t;a-=t;
        t=min(c/2,a);
        ans+=t;
        c-=t*2;a-=t;
        ans+=c/3;
        cout<<ans<<endl;
    }
    return 0;
}

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

using namespace std;

#define MOD 1000000007

int main(){
  int n,d; cin >> n >> d;
  int flag=0;
  for(int i=0;i<n;++i){
    int a; cin >> a;
    a--;
    a%=d+1;
    flag^=a;
  }
  if(flag) cout << "First" << endl;
  else cout << "Second" << endl;
  
  return 0;
}


Measured memory_bytes: 3080
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <climits>
#include <queue>
#include <bitset>
#include <complex>
#include <stack>
#include <unordered_set>

using namespace std;

//#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define len(v) (int)v.size()
#define pii pair<int, int>
#define x first
#define y second

typedef long double ld;
typedef long long ll;

signed main() {
    
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, m, k;
    cin >> n >> m >> k;
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            int total = i * m + j * n - 2 * i * j;
            if (total == k) {
                cout << "Yes";
                exit(0);
            }
        }
    }
    
    cout << "No";
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin,(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;

int d[10][10];
void warshall_floyd(int n) {
  for (int k = 0; k < n; k++){       // 経由する頂点
    for (int i = 0; i < n; i++) {    // 始点
      for (int j = 0; j < n; j++) {  // 終点
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}
int main(){
    int h,w;
    cin >> h >> w;
    REP(i,10){
        REP(j,10){
            cin >> d[i][j];
        }
    }
    int a;
    int ans = 0;
    warshall_floyd(10);
    REP(i,h){
        REP(j,w){
            cin >> a;
            if(a != -1)
                ans += d[a][1];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    char s[200001];
    char t[200001];
    int i;
    int count;
    scanf("%s",s);
    scanf("%s",t);
    count=0;
    for(i=0;s[i]!='\0';++i){
        if(s[i]!=t[i]){
            ++count;
        }
    }
    printf("%d\n",count);
    return 0;
}

Measured memory_bytes: 2120
n=int(input())
a=input().split()
a=list(map(int,a))
ans=1
if(0 in a):
    print(0)
    exit()

for calc in a:
    ans*=calc
    if(ans>10**18):
        print(-1)
        exit()
if(ans>10**18):
    print(-1)
else:
    print(ans)


Measured memory_bytes: 21668
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=998244353;


int main(void){
    int n;
    cin>>n;
    vector<int> L(n,0);
    rep(i,n) cin>>L[i];
    int ans=0;
    //sort(L.begin(),L.end());
    rep(i,n){
        rep(j,n){
            rep(k,n){
                int a=L[i],b=L[j],c=L[k];
                //cout<<i<<" "<<i+j+1<<" "<<i+j+k+2<<endl;
                if(a==b || b==c || c==a) continue;
                if(a+b>c && b+c>a && c+a>b){
                    //cout<<i<<" "<<i+j<<" "<<i+j+k<<endl;
                    ans++;
                }
            }
        }
    }
    cout<<ans/6<<endl;
    return 0;
}

Measured memory_bytes: 3636
#pragma region template
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
constexpr ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
constexpr ll LCM(ll a, ll b) { return a / GCD(a, b) * b; }
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) {
      cout << " ";
    }
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) {
        cout << " ";
      }
    }
    if (&v != &vv.back()) {
      cout << "\n";
    }
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) {
    cout << (f ? " " : "\n");
  }
  print(forward<Tail>(tail)...);
}
#pragma endregion

void Pr(bool f){
  cout << (f ? "Yes" : "No") << "\n";
  exit(0);
}

ll dp[200010][5];

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll n;
  cin >> n;
  vll a(n);
  rep(i, n){
    cin >> a[i];
  }
  a.emplace_back(0);
  rep(i, 200010)rep(j, 5) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i, n+1){
    rep(j, 5){
      ll mi = INF;
      rep(k, j+1){
        chmin(mi, dp[i][k]);
      }
      ll d;
      if(j == 0 || j == 4) d = a[i];
      if(j == 1 || j == 3) d = a[i] == 0 ? 2 : a[i]%2;
      if(j == 2) d = 1 - a[i]%2;
      chmin(dp[i+1][j], mi+d);
    }
  }
  print(dp[n+1][4]);
}


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

#define ll long long int
#define ff first 
#define ss second
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr (i,a,b) for(i=a;i<b;i++)
#define vi vector <ll>
#define ii pair<ll,ll>
#define vii vector<ii>
#define mp make_pair
#define pb push_back

using namespace std;

const ll MAXN = 1e5+8;
const ll LOGN = 17;
const ll ROOTN = 320;
const ll MOD = 1e9+7;
const ll INF = 1e17+8;

int main()
{
	string S;
	ll K,i,j=0,ans=0;
	cin>>S>>K;
	vi v;
	char t = S[0];
	bool same = true;
	FOR(i,S.size())
		if (S[i] != t)
		{
			same = false;
			break;
		}
	if (same)
	{
		j = (K*S.size())/2;
		cout<<j;
		exit(0);
	}
	FOR(i,S.size())
	{
		if (i == 0)
		{
			t = S[0];
			j++;
			continue;
		}
		if (t != S[i])
		{
			v.pb(j);
			ans += j/2;
			j = 0;
		}
		t = S[i];
		j++;
	}
	v.pb(j);
	ans += j/2;
	if (S[0] != S[S.size() - 1] or (v[0]%2 == 0 or v[v.size() - 1]%2 == 0))
		cout<<K*ans;
	else
		cout<<K*ans + K - 1;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a;
	scanf("%d",&a);
	long long ans=0;
	for(int i=1;i<=a;i++){
		if(i%3!=0&&i%5!=0)ans+=i;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	bool ch=true;
	ll n;
	cin>>n;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		if(now%2==0){
			if(now%3!=0&&now%5!=0){
				ch=false;
			}
		}
	}
	if(ch){
		cout << "APPROVED";
	}
	else{
		cout << "DENIED";
	}
	// your code goes here
	return 0;
}

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


string maxi(string s){

	  vector<string> tmp;
	  for(int i=0; i<s.size(); i++)
			tmp.push_back(s.substr(i,1));
	  sort(tmp.begin(),tmp.end());
	  reverse(tmp.begin(),tmp.end());
	  string ans = "";
	  for(int i=0; i<s.size(); i++)
			ans += tmp[i];
	  return ans;
}

string mini(string s){
	  vector<string> tmp;
	  for(int i=0; i<s.size(); i++)
			tmp.push_back(s.substr(i,1));
	  sort(tmp.begin(),tmp.end());
//	  reverse(tmp.begin(),tmp.end());
	  string ans = "";
	  for(int i=0; i<s.size(); i++)
			ans += tmp[i];
	  return ans;
}

int main(){
	  while(1){
			string a;
			int L;
			cin >> a >> L;
			if(!L) break;
			while( a.size() < L )  a = "0" + a;
			
			vector<string> list(1,a);

			while(1){
				  a = to_string(stoi(maxi(a)) - stoi(mini(a)));
				  while( a.size() < L )	a = "0" + a;
				  for(int i=0; i<list.size(); i++)
						if(a == list[i]){
							  cout << i << " " << stoi(a) << " " << list.size() - i << endl;
							  goto L1;
						}
				  list.push_back(a);
								  
			}
	  L1:;
	  }
	  return 0;
}

Measured memory_bytes: 3224
N,M=[int(z) for z in input().split(" ")]
d=[]

for z in range(0,N):
  d.append([int(z) for z in input().split(" ")])

r=M
ans=0
for z in sorted(d):
  if r==0:
    break
  if z[1]<=r:
     ans+=z[0]*z[1]
     r-=z[1]
  else:
    ans+=z[0]*r
    r=0

print("{:d}".format(ans))

Measured memory_bytes: 22376
n = int(input())
d = {}

for i in range(1, n+1):
	s, p = input().split()
	p = int(p)
	if s in d:
		d[s][p] = i
	else:
		d[s] = {}
		d[s][p] = i

for i in sorted(d.keys()):  
	for j in sorted(d[i].keys(), reverse=True):
		print(d[i][j])

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <array>
#include<unordered_map>
#include<unordered_set>

using namespace std;
#define IO                 \
	ios::sync_with_stdio(0); \
cin.tie(0);              \
cout.tie(0);
#define forn(i, n) for (int i = 0; i < n; i++)
#define forse(i, s, e) for (int i = s; i < e; i++)
#define pb push_back
#define pf push_front
#define rb pop_back
#define rf pop_front
#define mp make_pair
#define fi first
#define se second
#define all(vec) vec.begin(), vec.end()
#define getcurrtime() \
	cerr << "Time = " << ((double)clock() / CLOCKS_PER_SEC) << endl

#define watch(x) cerr << (#x) << " is " << (x) << endl;

#ifndef LOCAL
#define cerr if(false)cerr
#endif
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll P=1e9+7;
double PI=3.141592653589793;
const int arrn = 4e6 + 1;


void solve(){
	ll a,b,n;
	cin >> a >> b >> n;
	n=min(b-1,n);
	ll ans=0;
	if(a<b){
		ans=max(ans,(a*n)/b);
	}else{
		forse(i,1,n+1){
			ans=max(ans,(a*i)/b);
		}
	}
	cout << ans;
}

int main() {
	IO;
	int T=1;
//	cin >> T;
	forn(c,T){
		solve();
	}
}



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

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

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

int main(void){

    int h, w;
    cin >> h >> w;
    vector<vector<int>> mat(h, vector<int>(w));
    vector<int> b(w, 0);
    vector<int> ans(h, 0);
    roop(i, h){
        roop(j, w){
            cin >> mat[i][j];
        }
    }

    roop(i, w) cin >> b[i];

    roop(i, h){
        roop(j, w){
            ans[i] += mat[i][j] * b[j];
        }
    }

    roop(i, h){
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3168
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())
nsl = lambda: list(nsm())

mod = 1000000007

n, m = nm()
dp = [0] * (n + 1)
for i in range(m):
    tmp = ni()
    dp[tmp] = -1
dp[0] = 1
for i in range(n):
    if i + 1 < n + 1:
        if dp[i + 1] != -1 and dp[i] != -1:
            dp[i + 1] += dp[i] % mod
            dp[i + 1] %= mod
    if i + 2 < n + 1:
        if dp[i + 2] != -1 and dp[i] != -1:
            dp[i + 2] += dp[i] % mod
            dp[i + 2] %= mod
print(dp[n] % mod)


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

int main() {
	int n;
  cin>>n;
  	int d[n];
  
  
  rep(i,n)cin>>d[i];
  
  sort (d,d+n);
  
  int p=n/2;
  int q=n/2-1;
  int ans=0;
  
  if(d[q]==d[p])cout<<0<<endl;
  
  else{
  for(int i=d[q];i<d[p];i++){
	ans++;
  }
  
  cout<<ans<<endl;
  }
  }


Measured memory_bytes: 3996
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <sstream>
#include <fstream>

using namespace std;

#define A first
#define B second
#define all(x) (x).begin(), (x).end

typedef long long ll;
constexpr int MOD = 1000000007;
constexpr int MAX_SIZE = 100001;

void solve() {
  int N, W;
  cin >> N >> W;
  vector<int> w(N), v(N);
  for(int i = 0; i < N; i++){
    cin >> w[i] >> v[i];
  }
  vector<vector<ll>> dp(N, vector<ll>(MAX_SIZE));
  for(int i = 0; i < N; i++){
    for(int j = 0; j < MAX_SIZE; j++){
      dp[i][j] = 1e18;
    }
  }

  for(int i = 0; i < N; i++){
    if(i == 0){
      dp[i][0] = 0;
      dp[i][v[0]] = w[0];
      continue;
    }
    for(int j = 0; j < MAX_SIZE; j++){
      if(j == 0){
        dp[i][j] = 0;
        continue;
      }
      dp[i][j] = dp[i - 1][j];
      if(j >= v[i]){
        dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
      }
    }
  }
  ll ans = 0;
  for(int i = MAX_SIZE - 1; i >= 0; i--){
    if(dp[N - 1][i] <= W){
      ans = i;
      break;
    }
  }
  cout << ans;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  T = 1;
  //cin >> T;
  while(T--){
    solve();
  }
}


Measured memory_bytes: 82340
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <functional>
#include <queue>
#include <unordered_set>
#include <climits>
#include <set>
#include <list>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

ll N, K;
ll A[200200];

bool IsCuttable(ll len){
	ll count = 0;
	for(int i = 0; i < N; i++){
		ll count_ = A[i] / len;
		if(A[i] % len != 0 && A[i] > len){
			count_++;
		}
		if(count_ > 0){
			count_--;
		}
		count += count_;
	}
	if(count <= K){
		return true;
	}else{
		return false;
	}
}

int main()
{
	cin >> N >> K;
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}
	
	ll min = 1;
	ll max = 1000000000;
	while( max - min > 0){
		ll mid = min + (max - min) / 2;
		//cout << mid << endl;
		if(IsCuttable(mid)){
			max = mid;
		}else{
			min = mid + 1;
		}
	}
	cout << min << endl;
	return 0;
}


Measured memory_bytes: 5128
#include <iostream>

using namespace std;

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

    if(s == "ABC") {
        cout << "ARC" << endl;
        return 0;
    } else if(s == "ARC") {
        cout << "ABC" << endl;
        return 0;
    }
    return 0;
}


Measured memory_bytes: 3128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp11
{
    class Class17
    {
        static void Main()
        {
            int N =int.Parse( Console.ReadLine());
            List<string> S = new List<string>();
            Dictionary<string, int> D = new Dictionary<string, int>();
            int[] T = new int[N];
            for(int i = 0; i < N; i++)
            {
                var ST = Console.ReadLine().Split();
                D.Add(ST[0], i);
                T[i] = int.Parse(ST[1]);
            }
            string X = Console.ReadLine();

            int t = D[X]+1;
            int ans = 0;
            for (; t < N; t++)
            {
                ans += T[t];
            }

            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
n = int(input())
h_li = list(map(int,input().split()))

cnt = 0

while sum(h_li) != 0:
    check = 0
    for i in range(n):
        
        if h_li[i] > 0:
            h_li[i] -= 1
            check = 1
    
        else:
            if check == 1:
                cnt += 1
                check = 0
    else:
        if check == 1:
            cnt += 1
            
print(cnt)

Measured memory_bytes: 3060
fn main() {
    let s = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    };
    let (n, k, q) = {
        let mut ws = s.split_whitespace();
        let n: i64 = ws.next().unwrap().parse().unwrap();
        let k: i64 = ws.next().unwrap().parse().unwrap();
        let q: i64 = ws.next().unwrap().parse().unwrap();
        (n, k, q)
    };

    let mut a: Vec<i64> = Vec::new();
    for i in 0..q {
        let s = {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).unwrap();
            s.trim_right().to_owned()
        };
        let a_i: i64 = s.parse().unwrap();
        a.push(a_i)
    }
    // println!("{:?}", a);

    let mut counts = vec![0; n as usize];
    // println!("{:?}", counts);
    for x in a {
        // let person_count = counts.get((x - 1) as usize);
        // counts.push(x - 1) = person_count + 1;
        if let Some(elem) = counts.get_mut((x - 1) as usize) {
            *elem += 1;
        }
    }
    // println!("{:?}", counts);

    for i in 0..n {
        if k - q + counts.get(i as usize).unwrap() > 0 {
            println!("Yes")
        } else {
            println!("No")
        }
    }
}


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

typedef long long ll;

struct BIT{
  int size;
  vector< ll > t;
  void init(int n){
    size=n;
    t.resize(n,0);
  }

  void add(int i,ll x){
    i++;
    while( i < size ){
      t[i]+=x;
      i+=(i&-i);
    }
  }

  ll sum(int i){
    i++;
    ll res=0;
    while(i){
      res+=t[i];
      i-=(i&-i);
    }
    return res;
  }
};



int n;
char c[4000];
int a[4000];

int B[2000];
int W[2000];

int dp[2005][2005];
int countW[2005][2005];
int countB[2005][2005];

int main(){
  cin>>n;
  
  for(int i=0;i<n*2;i++){
    cin>>c[i]>>a[i];
    a[i]--;
    if(c[i]=='B')B[ a[i] ]=i;
    if(c[i]=='W')W[ a[i] ]=i;
  }
  
  for(int i=0;i<=n;i++){
    BIT T;
    T.init(5000);    
    for(int j=0;j<4500;j++)T.add(j,1);
    for(int j=0;j<i;j++)T.add(B[j],-1);
    
    for(int j=0;j<n;j++){
      T.add(W[j],-1);
      countW[i][j]=T.sum(W[j]);
    }
  }
  
  for(int i=0;i<=n;i++){
    BIT T;
    T.init(5000);    
    for(int j=0;j<4500;j++)T.add(j,1);
    for(int j=0;j<i;j++)T.add(W[j],-1);
    
    for(int j=0;j<n;j++){
      T.add(B[j],-1);
      countB[j][i]=T.sum(B[j]);
    }
  }
  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
      dp[i][j]=1e9;
  
  dp[0][0]=0;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      //      cout<<i<<j<<' '<<countW[i][j]<<' '<<countB[i][j]<<endl;
      if(j<n)
        dp[i][j+1]=min(dp[i][j+1], dp[i][j]+countW[i][j] );
      
      if(i<n)
        dp[i+1][j]=min(dp[i+1][j], dp[i][j]+countB[i][j] );
    }
  }
  cout<<dp[n][n]<<endl;
  return 0;
}


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

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

using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    if(a * b <= c) cout << a * b << endl;
    else cout << c << endl;
    
}









Measured memory_bytes: 3612
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

int main() {
    int n, sum = 0;
    cin >> n;
    vector<int> a(n+2, 0), m(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    rep(i, n+1) {
        m[i] = abs(a[i+1] - a[i]);
        sum += m[i];
    }


    for (int i = 1; i <= n; i++) {
        cout << sum - m[i-1] - m[i] + abs(a[i+1] - a[i-1]) << endl;
    }

    return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
typedef long long ll;
using namespace std;
vector<ll> v(3333);
ll dp[3333][3333];

ll f(int l,int r){
    if(l==r)return v[l];
    if(l>r)return 0;
    if(dp[l][r]!=-1)return dp[l][r];
    return dp[l][r]=max(v[l]-f(l+1,r),v[r]-f(l,r-1));
}

int main(){
    int n;cin>>n;
    for(auto &i:v)cin>>i;
    for(int i=0;i<3333;i++)for(int j=0;j<3333;j++)dp[i][j]=-1;
    cout<<f(0,n-1);
}

Measured memory_bytes: 87168
#include <iostream>
using namespace std;
    int main(void){
        long n, i, input, max=-1000000, min=1000000, sum=0;
        const char space = ' ';

        cin >> n;
        for( i = 0; i < n; i++){
            cin >> input;
            if( input > max ){
                max = input;
            }
            if( input < min ){
                min = input;
            }
            sum += input;
        }

        cout << min << space << max << space << sum << endl;

    }


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

typedef complex<double> Point;

vector<Point> e = {{+1,0}, {0,+1}, {-1,0}, {0,-1}};
string dir[4] = {"R","U","L","D"};

string command(Point cur, Point goal,int arm){
    if(arm == 0){
        if(abs(cur - goal) < 1e-4) return "";
        else arm = 1;
    }

    double min_dist = 2e9;
    int d;
    Point min_nxt;
    rep(i,4){
        Point nxt = cur + e[i]*(double)arm;
        if (min_dist > abs(goal - nxt)){
            min_dist = abs(goal - nxt);
            min_nxt = nxt;
            d = i;
        }
    }
    return dir[d] + command(min_nxt, goal, arm/2);
}

int main(void){
    int n;
    cin>>n;
    vector<Point> ps(n);
    set<int> even_odd;
    rep(i,n){
        int x,y;
        cin>>x>>y;
        ps[i] = Point(x,y);
        even_odd.insert((abs(x+y))&1);
    }
    if(even_odd.size()!=1){
        cout<<-1<<endl;
        return 0;
    }

    vector<string> commands(n);
    rep(i,n){
        commands[i] = command(Point(0,0), ps[i], 1<<30);
    }
    int m = commands[0].size();
    cout<<m<<endl;
    int arm = 1<<30;
    rep(i,m){
        cout<<arm<<(i == m-1 ? "\n": " ");
        arm = arm==1 ? 1 : arm/2;
    }
    rep(i,n) cout<<commands[i]<<endl;

    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <vector <int>> vvi;
typedef vector <vector <long long>> vvll;
typedef vector <long long> vll;
typedef pair <int, int> pii;
typedef pair<ll , ll> pll;
typedef vector <pair <int, int>> vpii;

int main()
{
    string a, b; cin >> a >> b;
    int al = a.length(), bl = b.length();
    vvi state(al + 1, vi (bl + 1, 0));

    for(int i = 1; i < al + 1; i++)
        for(int j = 1; j < bl +1; j++ )
        {
            if(a[i-1] == b[j-1]) state[i][j] = state[i-1][j-1] + 1;
            else state[i][j] = max(state[i-1][j], state[i][j-1]);
        }

    string res;
    int i = al, j = bl;
    while (i != 0 && j != 0)
    {
        i = (i >= 0)? i: 0;
        j = (j >= 0)? j: 0;
        if(a[i-1] == b[j-1]) {
            i--; j--;
            res = a[i] + res; 
        }
        else
        {
            if(state[i-1][j] > state[i][j-1])
            {
                i--;
            }
            else j--;
        }

    }
    
    cout << res << endl;
}

Measured memory_bytes: 35584
/*
				C++
				encoding: UTF-8
				Last Modified: 22/Aug/20 05:34:26 PM
*/

#include <bits/stdc++.h>
#ifdef H4wk3ye
#	include <prettypr.hpp>
#endif

using namespace std;

#define int int64_t

template < typename T > void print (const T& t) {
	cout << t << '\n';
}

template < typename T, typename U, typename... ARGS >
void print (const T& t, const U& u, const ARGS&... args) {
	cout << t << " ";
	print (u, args...);
}

signed main () {
	ios_base::sync_with_stdio (false), cin.tie (nullptr);
	string s;
	cin >> s;
	int c = 0;
	for (auto i : s) {
		int x = i - '0';
		c += x % 9;
		c %= 9;
	}
	print (!c ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 3744
#include<bits/stdc++.h>
using namespace std;
#define F(i,s,e) for(int i=s;i<e;++i)
#define ll long long

int main()
{
    int A,B,M;
    cin >> A >> B >> M;
    int a[A],b[B],mina=1e9,minb=1e9;
    F(i,0,A){
        cin >> a[i];
        if(mina>a[i]) mina=a[i];
    }
    F(i,0,B){
        cin >> b[i];
        if(minb>b[i]) minb=b[i];
    }
    int ans = mina + minb;
    int x,y,c;
    F(i,0,M){
        int sum=0;
        cin >> x >> y >> c;
        sum = a[x-1] + b[y-1] - c;
        if(ans>sum) ans=sum;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include  <iostream>
using namespace std;
int main()
{
    int x,y;
    cin>>x;cin>>y;
    if(x%3!=0&&y%3!=0)
        if((x+y)%3!=0)
            cout<<"Impossible";
        else
            cout<<"Possible";
    else
        cout<<"Possible";
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdlib>
#include <cmath>
#include<stdio.h>
#include<queue>
#include<stack>
#include<set>
#define MAX 1000000000000000000LL
long long inf=1000000007;
using namespace std;
using ll=long long;


int main(){
    int n; cin>>n;
    int max=1;
    while(1){
        max*=2;
        if(max>n){
            cout<<max/2<<endl;
            break;
        }
    }
    return 0;
    
}

Measured memory_bytes: 256
n = int(input())
v = input().split()
for i in range(len(v)):
    v[i] = int(v[i])
nums = [[],[]]
fr = [[],[]]
for i in range(len(v)):
    idx = (i+1)%2
    if v[i] in nums[idx]:
        fr_idx = nums[idx].index(v[i])
        fr[idx][fr_idx] += 1
    else:
        nums[idx].append(v[i])
        fr[idx].append(1)
        


fr_sort = [[0,0,0,0]+sorted(fr[0]),[0,0,0,0]+sorted(fr[1])]
maxfr = [fr_sort[0][-1],fr_sort[1][-1],fr_sort[0][-2],fr_sort[1][-2]]
maxnum = [[],[],[],[]]

for i in [0,1,2,3]:
    for j in range(len(nums[i%2])):
        if fr[i%2][j] == maxfr[i]:
            maxnum[i].append(nums[i%2][j])
                   
if maxnum[0] == maxnum[1]:
    m = max([maxfr[0]+maxfr[3],maxfr[1]+maxfr[2]])
else:
    m = maxfr[0] + maxfr[1]
                   
print(n-m)

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

void solve(){
int n;
cin>>n;
ll a[n];
rep(i,n) cin>>a[i];
ll ans=0;
for(int i=0;i<n;i++){
	if(i>0){
		if(a[i]<a[i-1]) {ans+=(a[i-1]-a[i]);
		a[i]=a[i-1];
		}
	}
}
cout<<ans;
}
int main() {
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 5184
S = input()
T = input()
slist,tlist = {},{}
S2,T2 = [],[]
scount,tcount = 0,0

for i in range(len(S)):
  if S[i] not in slist.keys():
    slist[S[i]] = scount
    scount += 1
  S2.append(slist[S[i]]) 

  if T[i] not in tlist.keys():
    tlist[T[i]] = tcount
    tcount += 1
  T2.append(tlist[T[i]]) 
#print(S2,T2,sep="\n")
if S2 == T2:
  print("Yes")
else:
  print("No")

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

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> ans(n);

  rep(_, 2) {
    int cnt = 0;
    rep(i, n) {
      if (s[i] == 'R')
        cnt++;
      else {
        ans[i] += cnt / 2;
        ans[i - 1] += (cnt + 1) / 2;
        cnt = 0;
      }
    }

    reverse(ans.begin(), ans.end());
    reverse(s.begin(), s.end());
    rep(i, n) {
      if (s[i] == 'L') s[i] = 'R';
      else
        s[i] = 'L';
    }
  }

  rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');

  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class Point{
public:
	double x,y;
	Point(){}
	Point(double xx,double yy){
		x=xx;
		y=yy;
	}
	Point operator+(Point p){
		return Point(x+p.x,y+p.y);
	}
	Point operator-(Point p){
		return Point(x-p.x,y-p.y);
	}
	Point operator*(double a){
		return Point(a*x,a*y);
	}
	Point operator/(double a){
		return Point(x/a,y/a);
	}

	double abs(){
		return sqrt(norm());
	}
	double norm(){
		return x*x+y*y;
	}
	bool operator<(const Point &p)const{
		return x!=p.x ? x<p.x:y<p.y;
	}
	bool operator==(const Point &p)const{
		return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
	}
};

typedef Point Vector;
struct Segment{
	Point p1,p2;
	Segment(){}
	Segment(Point pp1,Point pp2){
		p1=pp1;
		p2=pp2;
	}
};

typedef Segment Line;

double norm(Vector v){
	return v.x*v.x+v.y*v.y;
}

double abs(Vector v){
	return sqrt(norm(v));
}

double dot(Vector a,Vector b){
	return a.x*b.x+a.y*b.y;
}

double cross(Vector a,Vector b){
	return a.x*b.y-a.y*b.x;
}

int ccw(Point p0,Point p1,Point p2){
	Vector a=p1-p0;
	Vector b=p2-p0;
	if(cross(a,b)>EPS)return 1;
	if(cross(a,b)<-EPS)return -1;
	if(dot(a,b)<-EPS)return 2;
	if(a.norm()<b.norm())-2;
	return 0;
}

int n,m;
Point p[2][101];
typedef pair<Point,int> PP;

bool check(Point p0,Point p1){
	int side=0;
	vector<PP> vec;
	for(int i=0;i<n;i++){
		int v=ccw(p0,p1,p[0][i]);
		if(abs(v)!=1)vec.push_back(PP(p[0][i],0));
		else{
			if(side!=0 && side!=v)return false;
			side=v;
		}
	}
	int side2=0;
	for(int i=0;i<m;i++){
		int v=ccw(p0,p1,p[1][i]);
		if(abs(v)!=1)vec.push_back(PP(p[1][i],1));
		else{
			if(side2!=0 && side2!=v)return false;
			side2=v;
		}
	}
	if(side==side2 && side!=0)return false;
	sort(vec.begin(),vec.end());
	int ch=0;
	for(int i=1;i<vec.size();i++){
		if(vec[i].second!=vec[i-1].second)ch++;
	}
	return ch<=1;
}

bool solve(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(check(p[0][i],p[1][j]))return true;
		}
	}
	return false;
}

int main(void){
	while(1){
		scanf("%d%d",&n,&m);
		for(int i=0;i<n;i++){
			scanf("%lf%lf",&p[0][i].x,&p[0][i].y);
		}
		for(int i=0;i<m;i++){
			scanf("%lf%lf",&p[1][i].x,&p[1][i].y);
		}
		if(n==0 && m==0)break;
		printf("%s\n",solve()?"YES":"NO");
	}
	return 0;
}


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

int main(){
	int n,x;cin>>n>>x;
	vector<int>v(n);
	for(auto&& u:v)cin>>u;
	sort(begin(v),end(v));
	int sm=0,cnt=0;
	for(auto&& u:v){
		sm+=u;
		if(sm<=x)cnt++;
		else break;
	}
	if(cnt==n&&sm<x)cnt--;

	cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;

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

vector<long long int>dp(N+1);
dp[0]=1;
for(int x=0;x<N;x++){
for(int y=x+1;y<=min(N,x+2);y++){
if(A[y]){
dp[y]+=dp[x];
dp[y]%=mod;
}
}
}

cout<<dp[N]<<endl;
}


Measured memory_bytes: 1408
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    ans = 0
    n = input()
    dp = [0,1] #0,1多く入れる
    for i in n:
        ni = int(i)
        pdp = dp*1
        dp[0] = min(pdp[0]+ni,pdp[1]+(10-ni))
        dp[1] = min(pdp[0]+ni+1,pdp[1]+(10-ni-1))
    print(dp[0])


    return None

if __name__ == '__main__':
    main()


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

int N, K;
int h[100010];
int dp[100010];

int main () {

    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d", &h[i]);
    }

    dp[0] = 0;
    for (int i = 1; i < N; i++) {
        int max_cost = 1000000007;
        for (int j = 1; j <= K; j++) {
            if (i - j < 0) continue;
            max_cost = min(max_cost, dp[i-j]+abs(h[i]-h[i-j]));
        }
        dp[i] = max_cost;
    }
    cout << dp[N-1] << endl;

    return 0;
}

Measured memory_bytes: 1024
import sys
import heapq

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = []
for i in range(N):
    heapq.heappush(Q, (-B[i], i))
ans = 0
cnt = 0

while len(Q) != 0:
    _, i = heapq.heappop(Q)

    if (B[i] - A[i]) % (B[(i-1) % N] + B[(i+1) % N]) == 0:
        ans += (B[i] - A[i]) // (B[(i-1) % N] + B[(i+1) % N])
        cnt += 1
        B[i] = A[i]
    else:
        tmp = (B[i] - 1) // (B[(i-1) % N] + B[(i+1) % N])
        
        if tmp == 0:
            print(-1)
            sys.exit()
        
        B[i] -= tmp * (B[(i-1) % N] + B[(i+1) % N])
        ans += tmp
        heapq.heappush(Q, (-B[i], i))
    
    if cnt == N:
        print(ans)
        sys.exit()

print(-1)

Measured memory_bytes: 134908
import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Integer> list = new ArrayList<>();
        for(int i = 1;i <= m/2;i++){
            if(m % i == 0){
                list.add(i);
            }
        }
        list.add(m);

        for(int i = list.size()-1;i >= 0;i--){
            int x = list.get(i);
            int t = m/x;
            if(t >= n){
                System.out.println(x);
                break;
            }
        }

    }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main(){
  char c;
  cin >> c;
  string str="aiueo";
  for(int j=0;j<5;j++)
    if(c == str.at(j)){
      cout << "vowel" << endl;
      return 0;
    }
  cout << "consonant" << endl;
}

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



int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    for(int i=0;i<N;i++){
        cin >> h.at(i);
    }
    int ans =0;
    int max = *max_element(h.begin(), h.end());
    
    for(int j = 0;j < max;j++){
        bool flag = true;
        for(int i=0;i<N;i++){
            if(h.at(i)>0 && flag){
                ans += 1;
                flag = false;
                h.at(i) -= 1;
            }
            else if(h.at(i) == 0){
                flag = true;
            }
            else{
                h.at(i) -= 1;
            }
        }
    }
    cout << ans << endl;
} 


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    int res = 0;
    while (x <= y) {
        res++;
        x <<= 1ll;
    }
    printf("%d", res);
    return 0;
}

Measured memory_bytes: 256
print((lambda a:min([min([1145148931919810 if a[1]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[0],(a[1]-i)*(a[0]//2),(a[1]-i)*(a[0]//2+(a[0]%2))])) for i in range(1, a[1])])]+[min([1145148931919810 if a[0]<=1 else (lambda b:b[2]-b[0])(sorted([i*a[1],(a[0]-i)*(a[1]//2),(a[0]-i)*(a[1]//2+(a[1]%2))])) for i in range(1, a[0])])]+[a[1] if a[0]%3 else 0]+[a[0] if a[1]%3 else 0]))(list(map(int,input().split()))))

Measured memory_bytes: 7372
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}
int read() {
	int tmp;
	cin >> tmp;
	return tmp;
}
int xor128() {
	static int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	int t = (x xor (x << 11));
	x = y; y = z; z = w;
	return (w = (w xor (w >> 19)) xor (t xor (t >> 8)));
}

signed main() {
	int n;
	cin >> n;
	while (1) {
		if (prime(n)) {
			cout << n << endl;
			return 0;
		}
		n++;
	}

	return 0;
}


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

int main()
{
    // ifstream cin("input.txt");
    int N;
    cin >> N;
    int ans = 0;
    for(int i=1;i<=N-1;i++)
    {
        ans += (N-1)/i;
    }
    cout << ans << endl;
    return 0;

}

Measured memory_bytes: 3644
#include<stdio.h>
int main()
{
	int a, b, d, r;
	double f;
	scanf("%d %d", &a, &b);
	d = a / b;
	r = a%b;
f=1.00000*a/b;
printf("%d %d %f\n",d,r,f);
return 0;
}


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

int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(abs(a-c) <= d) {
        cout << "Yes" << endl;
    }
    else if(abs(b-a) <= d && abs(c-b) <= d) {
        cout << "Yes" << endl;
    } 
    else cout << "No" << endl;
}

Measured memory_bytes: 256