akhauriyash/Code-Regression huggingface dataset:
#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;
}
void print() { cout << "\n"; }
template <class T> void print(const T &x) { cout << x << "\n"; }
template <class T, class... Args> void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
template <class T> void printVector(const vector<T> &v) {
    for(const T &x : v) {
        cout << x << " ";
    }
    cout << "\n";
}
using ll = long long;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
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};

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, n;
    cin >> x >> n;
    set<int> se;
    for(int i = 0; i < n; i++) {
        int p;
        cin >> p;
        se.insert(p);
    }
    int val = INF;
    int ans = -1;
    for(int i = -2000; i <= 2000; i++) {
        if(!se.count(i)) {
            if(val > abs(i - x)) {
                val = abs(i - x);
                ans = i;
            }
        }
    }
    print(ans);
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int r;cin>>r;
    if(r<1200) cout<<"ABC"<<endl;
    else if(r<2800) cout<<"ARC"<<endl;
    else cout<<"AGC"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;
using plll=pair<ll,pll>;
using graph=vector<vector<int>>;
using wgraph=vector<vector<pll>>;

const ll MOD=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p=LLONG_MAX){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

void pushHeap(vector<ll>& h,int n){
  int i=h.size();
  h.push_back(n);
  while(i!=0 && h[(i-1)/2]<h[i]){
    swap(h[i],h[(i-1)/2]);
    i=(i-1)/2;
  }
  h[i]=n;
}

ll popHeap(vector<ll>& h){
  int n=h.size()-1;
  if(n==-1)return 0;
  ll i,ret=h[0];
  swap(h[0],h[n]);
  h.pop_back();
  for(i=0;i<n;){
    int j=2*i+1;
    if(j>=n)break;
    if(j!=n-1 && h[j]<h[j+1])j++;
    if(h[i]<h[j]){
      swap(h[i],h[j]);
    }
    i=j;
  }
  return ret;
}

int bis(vector<int> v,int key){
  int left=-1,right=v.size();
  while(abs1(right-left)>1){
    int mid=left+(right-left)/2;
    if(v[mid]<=key)left=mid;
    else right=mid;
  }
  return left;
}

int main(){
  int i,j,k,cnt=0;
  ll a,b;
  cin>>a>>b;
  cout<<a*b/gcd1(a,b)<<endl;
}

Measured memory_bytes: 256
//\\                            ||                     ||
            ////          //  \\                           ||                     ||
                         //    \\          //\\    //\\    ||                     ||
            ////        //      \\       //   \\  //  \\   ||                     ||
            ////       ____________     ||     \\//    ||  ||_______      ________||
            ////      //          \\    ||             ||  ||______\\    //_______||
            ////     //            \\   ||             ||  ||       ||   ||       ||
            ////    //              \\  ||             ||  ||_______||   ||_______||
            ////   //                \\ ||             ||  ||______//     \\______||







                     /*WHO CARES IF ONE MORE LIGHT GOES OUT ?
                           IN A SKY OF A MILLION STARS
                               IT FLICKERS,FLICKERS
                       WHO CARES WHEN SOMEONE'S TIME RUNS OUT ?
                            IF A MOMENT IS ALL WE ARE.
                       WHO CARES IF ONE MORE LIGHT GOES OUT ?
                                WELL I DO...*/
#include<bits/stdc++.h>
using namespace std;
long long int fa[1022];

long long int powe(long long int d,long long int s)
{
    if(s==1) return d;
    else if(s==0) return 1;
    else
    {
        long long int u,v=d;
        for(u=1;u<s;u++)
        {
            d=d*v;
        }
        return d;
    }
}
long long int phi(long long int n)
{
    double result=n;
    for (long long int p=2;p*p<=n;++p){
        if (n%p==0){
            while(n%p==0)
                n/=p;
            result*=(1.0-(1.0/(double)p));
        }
    }
    if(n>1)
        result*=(1.0-(1.0/(double)n));

    return (long long int)result;
}
long long int bigmod(long long int a, long long int b,long long int m)
{
    long long int r;
    if(b==0) return 1;
    if(b%2==0) { r=(r*r)%m;
        return  r;
    }
        return ((a%m)*bigmod(a,b-1,m)%m)%m;
}
int main()
{
    map<string,long long int>mp;
    long long int a,b;
    cin>>a>>b;
    if(b>=a) cout<<"unsafe"<<endl;
    else cout<<"safe"<<endl;




    return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int main(){
  int n,d,x;
  cin>>n>>d>>x;
  if(d==1){
    cout<<x<<endl;
    return 0;
  }

  int table[d][n];
  int dp[110000];

  rep(i,d){
    rep(j,n){
      cin>>table[i][j];
    }
  }

  int ans = x;

  rep(day,d-1){
    memset(dp,0,sizeof(dp));
    rep(i,ans+1) dp[i]=i;
    int tmp = ans;
    rep(i,n){
      FOR(j,table[day][i],ans+1){
        dp[j]=max(dp[j],dp[j-table[day][i]]+table[day+1][i]);
        tmp = max(tmp,dp[j]);
      }
    }
    ans = tmp;
  }


  cout<<ans<<endl;
}



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

int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> child(n);
  vector<int> parent(n);
  rep(i, n) parent[i] = 0;
  int x, y;
  rep(i, m) {
    cin >> x >> y;
    x--; y--;
    parent[y]++;
    child[x].push_back(y);
  }
  
  vector<int> dp(n);
  queue<int> nodes;
  rep(i, n) {if (parent[i] == 0) nodes.push(i); dp[i] = 0;}
  
  while (nodes.size()) {
    int j = nodes.front(); nodes.pop();
    
    if (child[j].size() > 0)
    rep(k, child[j].size()) {
      int c = child[j][k];
      dp[c] = max(dp[j] + 1, dp[c]);
      parent[c]--;
      if (parent[c] == 0) nodes.push(c);
    }
  }
  
  int max = 0;
  rep(i, n) if (max < dp[i]) max = dp[i];
  cout << max << endl;
}


Measured memory_bytes: 6528
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;

P dp[32][32][32][32]; //dp[a][b][c][d]...(a,b),(a,d),(c,b),(c,d)で囲まれた長方形の分割数と予備力
int rui[33][33]; //2次元累積和
int u[32][32];
int h,w,s;

P operator+(const P& lhs, const P& rhs)
{
	return P(lhs.first+rhs.first,min(lhs.second,rhs.second));
}

//tate*yokoの場合を計算する
void memo(int tate,int yoko)
{
	for(int i=0;i<h-tate+1;i++)
	{
		for(int j=0;j<w-yoko+1;j++)
		{
			//dp[i][j][i+tate-1][j+yoko-1]
			//単体で何とかなるか確かめる
			int yutori=(rui[i+tate][j+yoko]-rui[i+tate][j]-rui[i][j+yoko]+rui[i][j])-(rui[h][w]-s);
			//cerr<<i<<" "<<j<<" "<<tate<<" "<<yoko<<" "<<yutori<<endl;
			if(yutori<0)
				continue;
			
			dp[i][j][i+tate-1][j+yoko-1]=P(1,yutori);
			//縦に分ける
			for(int k=1;k<tate;k++)
			{
				dp[i][j][i+tate-1][j+yoko-1]=max(dp[i][j][i+tate-1][j+yoko-1],dp[i][j][i+k-1][j+yoko-1]+dp[i+k][j][i+tate-1][j+yoko-1]);
				//cerr<<(dp[i][j][i+k-1][j+yoko-1]+dp[i+k][j][i+tate-1][j+yoko-1]).first<<endl;
			}
			//横に分ける
			for(int k=1;k<yoko;k++)
				dp[i][j][i+tate-1][j+yoko-1]=max(dp[i][j][i+tate-1][j+yoko-1],dp[i][j][i+tate-1][j+k-1]+dp[i][j+k][i+tate-1][j+yoko-1]);
		}
	}
}

int main()
{
	while(1)
	{
		cin>>h>>w>>s;
		if(h==0)
			break;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
				cin>>u[i][j];
		}
		//累積和の計算
		rui[0][0]=0;
		for(int i=1;i<w+1;i++)
			rui[0][i]=0;
		for(int i=1;i<h+1;i++)
			rui[i][0]=0;
		for(int i=1;i<h+1;i++)
		{
			for(int j=1;j<w+1;j++)
				rui[i][j]=rui[i][j-1]+u[i-1][j-1];
		}
		for(int j=1;j<w+1;j++)
		{
			for(int i=1;i<h+1;i++)
				rui[i][j]+=rui[i-1][j];
		}
		//ここまで累積和
		fill(dp[0][0][0],dp[32][0][0],P(-999,-1e8+1));
		for(int i=1;i<h+1;i++)
		{
			for(int j=1;j<w+1;j++)
				memo(i,j);
		}
		cout<<dp[0][0][h-1][w-1].first<<" "<<dp[0][0][h-1][w-1].second<<endl;
	}
	return 0;
}


Measured memory_bytes: 11296
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;


int main(){
    int n;
    cin >> n;
    int p[10], q[10];
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    for(int i = 0; i < n; i++){
        cin >> q[i];
    }

    vector<int> x(n, 0);
    iota(x.begin(), x.end(), 1);

    int a = 0, b = 0;
    do{
        bool ok = true;
        for(int i = 0; i < n; i++){
            if(x[i] != p[i]){
                ok = false;
                break;
            }
        }
        if(ok){
            break;
        }
        else{
            a++;
        }
    } while(next_permutation(x.begin(), x.end()));

    iota(x.begin(), x.end(), 1);

    do{
        bool ok = true;
        for(int i = 0; i < n; i++){
            if(x[i] != q[i]){
                ok = false;
                break;
            }
        }
        if(ok){
            break;
        }
        else{
            b++;
        }
    } while(next_permutation(x.begin(), x.end()));

    cout << max(a, b) - min(a, b) << endl;


    return 0;
}


Measured memory_bytes: 256
// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)1e5 + 5;
                 
int l[MAXN], r[MAXN];

ll ans;

int n;

void solve() {                   
    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &l[i], &r[i]);
    }

    sort(l, l + n + 1);
    reverse(l, l + n + 1);
    sort(r, r + n + 1);

    ll cur = 0;
                     
    for (int i = 0; i <= n; ++i) {
        cur += (l[i] - r[i]);
        ans = max(ans, cur << 1);
    }

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

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

int main()
{
    long n;
    string s;

    set<string> x[26];

    cin >> n;
    for (long i = 0; i < n; i++) {
        cin >> s;
        x[s[0] - 'a'].insert(s);
    }

    long sum = 0;

    for (int i = 0; i < 26; i++) {
        sum += x[i].size();
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 19204
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll a, b, c;
  in3(a, b, c);
  a = __gcd(a, b);
  if(c % a == 0)
    out("YES");
  else
    out("NO");
  memi;
}

Measured memory_bytes: 256
n = int(input())
s_li = [input() for i in range(n)]

ans = 0
s_dict = {}
for i in s_li :
    s_i = [ch for ch in i]
    s_i.sort()
    s_i = "".join(s_i)
    if s_i in s_dict :
        ans += s_dict[s_i]
        s_dict[s_i] += 1
    else :
        s_dict[s_i] = 1
print(ans)


Measured memory_bytes: 24976
def main():
    s = input()
    if s[0] == "A" and s.count("C", 2, -1)==1:
        s = s.replace("A", "")
        s = s.replace("C", "")
        if s.islower() == True:
            print("AC")
        else:
            print("WA")
    else:
        print("WA")
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define ll long long
#define P pair<int, int>
#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define GI(name) \
  int(name);     \
  scanf("%d", &(name))
#define GI2(name1, name2) \
  int(name1), (name2);    \
  scanf("%d %d", &(name1), &(name2))
#define GI3(name1, name2, name3) \
  int(name1), (name2), (name3);  \
  scanf("%d %d %d", &(name1), &(name2), &(name3))
#define GVI(name, size)    \
  vector<int>(name)(size); \
  FOR(i, (size)) scanf("%d", &(name)[i])
#define GS(name) \
  string(name);  \
  cin >> (name);
#define MOD 1000000007
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

string to_string(string s) {
  return s;
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  FOR(i, v.size() - 1) { ret += to_string(v[i]) + ","; }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() {
  cerr << endl;
}

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() {
  cout << endl;
}

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  GI3(W, H, N);
  int mnx = 0, mxx = W, mny = 0, mxy = H;
  FOR(i, N) {
    GI3(x, y, a);
    if (a == 1) {
      mnx = min(mxx, max(mnx, x));
    } else if (a == 2) {
      mxx = max(mnx, min(mxx, x));
    } else if (a == 3) {
      mny = max(mny, y);
    } else {
      mxy = min(mxy, y);
    }
  }
  print(max(0, (mxx - mnx) * (mxy - mny)));
  return 0;
}

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

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int, int>;
using vpii=vector<pii>;

template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>p){os<<"("<<p.fst<<", "<<p.scd<<")";return os;}
template<class T>ostream&operator<<(ostream&os,const vector<T>v){rep(i,v.size()){if(i)os<<", ";os<<v[i];}return os;}
template<typename T>T&max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T&min(T&a,T&b){if(a < b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a < b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a > b){a=b;return true;}return false;}
int in(){int a;scanf("%d",&a);return a;}
ll lin(){ll a;scanf("%lld",&a);return a;}

constexpr int inf = 1e9;
constexpr ll linf = 3e18;
constexpr double eps = 1e-9;

int n;
int a[200010], b[200010];
int bit[200010];
map<int, int> m;

int sum(int i)
{
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x)
{
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

int main()
{
    omajinai;

    cin >> n;

    rep(i, n) cin >> a[i], b[i] = a[i];

    sort(b, b+n);

    rep(i, n) {
        m[b[i]] = i+1;
    }

    ll ans = 0;

    rep(i, n) {
        ans += i - sum(m[a[i]]);
        add(m[a[i]], 1);
    }

    cout << ans << endl;
}

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

#define all(s) s.begin(), s.end()
#define vi vector<int>
#define pb push_back
#define ii pair<int, int>
#define x first
#define y second

string s[] = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string t;
    cin >> t;
    for (int i = 0; i < 7; i++) {
        if (t == s[i]) cout << 7 - i;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
typedef unsigned long long int ull;
typedef long double ldb;
typedef long long int ll;
 
#define for01(k,n)  for (ll i=k; i<n; i++)
#define for02(k,n)  for (ll j=k; j<n; j++)
#define for03(k,n)  for (ll k=k; k<n; k++)
#define for11(k,n)  for (ll i=k; i<=n; i++)
#define for12(k,n)  for (ll j=k; j<=n; j++)
#define for13(k,n)  for (ll k=k; k<=n; k++)
 
#define pb push_back
#define mp make_pair
#define pf push_front
#define popf pop_front
#define popb pop_back
#define vll vector<ll>
#define F first
#define S second
#define pp pair <ll, ll>
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define si size()
#define bk back()
#define deci(n)  fixed<<setprecision(n)
 
#define p0(a) cout << a << " "
#define p1(a) cout << a << "\n"
using namespace std;

int main(){
  int n;
  cin >> n;
  ll now_T = 0,now_A = 0;
 ll next1;
  
  for(int i = 0;i < n;i++){
    ll t,a;
    cin >> t >> a;
    if(now_T < t && now_A < a){
      now_T = t;
      now_A = a;
    }
    else{
      next1 = max((now_T + t - 1) / t,(now_A + a - 1) / a);
      now_T = t * next1;
      now_A = a * next1;
    }
    
    
  }
  
  cout << now_A + now_T << endl;
 
}

Measured memory_bytes: 256
M = 10 ** 9 + 7

# inverse
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

facts = [1]
facts_i = [1]
def cache_facts(n, M):
	f = 1
	fi = 1
	for i in range(1, n):
		f = (f * i) % M
		fi = (fi * calc_inverse(i, M)) % M
		facts.append(f)
		facts_i.append(fi)

def cached_C(a, b, M):
	return facts[a] * facts_i[a - b] * facts_i[b] % M

K = int(input())
S = input().strip()
L = len(S)

cache_facts(K + L + 1, M)

total = pow(26, K, M)

#print(total)
for i in range(1, K + 1):
	total = (total + (pow(25, i, M) * cached_C(L + i - 1, L - 1, M) % M) * pow(26, K - i, M)) % M

print(total)



Measured memory_bytes: 175184
"use strict";
process.stdin.resume();
process.stdin.setEncoding("utf8");

var input = [];
var reader = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on("line", line => {
  input.push(parseInt(line));
});

reader.on("close", () => {
  input.shift();
  let p = input;
  let sum = p.reduce((a, i) => a + i);
  let max = Math.max.apply(null, p)
  console.log(sum - max / 2);
});


Measured memory_bytes: 7628
#include <bits/stdc++.h>
using namespace std;
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using ll = long long;
constexpr i64 INF = 1010000000000000017LL;
constexpr i64 MOD = 1000000007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x; 
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x; 
        return true;
    }
    return false;
}
template<typename Val>
bool bitcheck(Val bit, size_t idx) {
    return bit & (1 << idx);
}
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr); ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH) cout << unitbuf;
    }
} PROCON_INIT;

void solve() {
    ll s; cin >> s;
    ll count = 1;
    ll now = s;

    while (now != 1 && now != 4 && now != 2) {
        if (now % 2 == 0) {
            now /= 2;
        } else {
            now = 3*now + 1;
        }
        ++count;
    }
    cout << count+3 << endl;
}

signed main() {
    solve();
    return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num::clamp;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        a: Chars
    }
    let n = a.len();

    let mut counts = HashMap::new();
    for c in a {
        *counts.entry(c).or_insert(0) += 1;
    }

    let mut ans = n * (n - 1) / 2 + 1;
    for &v in counts.values() {
        ans -= v * (v - 1) / 2;
    }
    println!("{}", ans);
}


Measured memory_bytes: 3132
#include <iostream>

using namespace std;

int main() {
    int n, dp[50];
    cin >> n;

    dp[0] = dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n] << endl;

    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define rep(i, x, N) for (long long i = x; i < (N); i++)
using namespace std;
int main()
{
	long long N, M;
	cin >> N >> M;
	vector<long long> a(M);
	vector<string> b(M);
	vector<pair<long long, string>> p(M);
	rep(i, 0, M)
	{
		cin >> a[i] >> b[i];
		p[i] = make_pair(a[i], b[i]);
	}
	long long H;
	H = max(N, M);
	vector<long long> flag(H), flag2(H);
	if (M > N)
	{

		rep(i, 0, M)
		{
			flag[i] = 0;
			flag2[i] = 0;
		}
	}
	else
	{
		rep(i, 0, N)
		{
			flag[i] = 0;
			flag2[i] = 0;
		}
	}
	rep(i, 0, M)
	{
		if (p[i].second == "AC")
		{
			flag2[p[i].first] = 1;
		}
	}
	long long count_ac = 0, count_wa = 0;
	rep(i, 0, M)
	{
		if (p[i].second == "AC" && flag[p[i].first] == 0)
		{
			flag[p[i].first] = 1;
			count_ac++;
		}
		else if (p[i].second == "WA" && flag[p[i].first] == 0 && flag2[p[i].first] == 1)
		{
			count_wa++;
		}
	}
	cout << count_ac << ' ' << count_wa << endl;
}


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

using namespace std;

int main(void){
    string s;
    int n;
    cin >> s;
    cin >> n;
    for(int i=0;i<s.size();i+=n){
        cout << s[i];
    }
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int wk;
    if (a > b) {
      wk = a;
      a  = b;
      b  = wk;
    }
    if (b > c) {
      wk = b;
      b  = c;
      c  = wk;
    }
    if (a > b) {
      wk = a;
      a  = b;
      b  = wk;
    }
    System.out.println(a+" "+b+" "+c);
  }
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const ll mod = 1e9 + 7;

bool compatible[22][22];
int n;

ll dp[22][(1<<22)];

ll recursion(int i, int mask) {
	if(dp[i][mask] != -1) return dp[i][mask];


	if(i == 0 && __builtin_popcount(mask) == 1) {
		for(int j=0;j<n;j++)
			if(mask&(1<<j))
				return dp[i][mask] = compatible[0][j];
	}
	else if(i == 0) return dp[i][mask] = 0;

	if(i+1 != __builtin_popcount(mask)) return dp[i][mask] = 0;

	dp[i][mask] = 0LL;
	for(int j=0;j<n;j++) {
		if(mask&(1<<j) && compatible[i][j]) {
			dp[i][mask] += recursion(i-1, mask^(1<<j));
			dp[i][mask] %= mod;
		}
	}
	return dp[i][mask];
}

int main() {
	cin>>n;
	for(int i=0;i<n;i++) {
		for(int j=0;j<n;j++) {
			cin>>compatible[i][j];
		}
	}

	memset(dp, -1, sizeof(dp));
	cout<<recursion(n-1, (1<<n)-1)<<"\n";
}

Measured memory_bytes: 721152
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }



int main()
{
	int a, b;
	char c;
	cin >> a >> c >> b;

	if (c == '+')
		cout << a + b << endl;
	else
		cout << a - b << endl;

}


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

int main(int argc, char *argv[]) {
	int dataN;
	//scanf("%d", &dataN);
	cin>>dataN;
	for (int i = 0; i < dataN; i++) {
		double ax, ay, ra, bx, by, rb;
		//scanf("%f %f %f %f %f %f", &ax, &ay, &ra, &bx, &by, &rb);
		cin>>ax>>ay>>ra>>bx>>by>>rb;
		double d = (ax-bx)*(ax-bx) + (ay-by)*(ay-by);

		d = sqrt(d);

		if (d+rb < ra) {
		  cout<<2<<endl;
		} else if (d+ra < rb) {
		  cout<<-2<<endl;
		} else if (d <= ra+rb) {
		  cout<<1<<endl;
		} else {
		  cout<<0<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
n = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(n)]

for i in range(n):
    ans[a[i]-1] = i+1

for i in range(n):
    print(ans[i], end=" ")


        



    










 

 


                                        




    




        


    







        



Measured memory_bytes: 14008
#include <iostream>

using namespace std;

int main(){
	int n, num[200];
	int box, times;
	
	cin >> n;

	for (int i = 0; i < n; i++){
		cin >> num[i];
	}

	box = 0;
	times = 0;

	for (int j = 0; j < n - 1; j++){
		for (int i = n - 1; i > 0; i--){
			if (num[i] < num[i - 1]){
				box = num[i];
				num[i] = num[i - 1];
				num[i - 1] = box;
				
				times++;
			}
		}
	}

	cout << num[0];
	for (int j = 1; j < n; j++){
		cout << " " << num[j];
	}

	cout << "\n" << times << endl;

}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

int pre[55];
int low[55];

int cnt = 0;

int dfs(const vvint &g, int v, int p = -1)
{
    for (const auto nv : g[v])
    {
        if (nv == p)
            continue;
        if (pre[nv] != -1)
        {
            low[v] = min(low[v], low[nv]);
            continue;
        }
        pre[nv] = pre[v] + 1;
        low[nv] = pre[nv];
        low[v] = min(dfs(g, nv, v), low[v]);
    }

    if (low[v] >= pre[v])
    {
        ++cnt;
    }
    return low[v];
}

void Main()
{
    arrayFill(pre, -1);
    arrayFill(low, INF);
    int n = in(), m = in();
    vvint g(n);
    rep(i, m)
    {
        int a = in(), b = in();
        --a;
        --b;
        g[a].pb(b);
        g[b].pb(a);
    }

    pre[0] = 0;
    low[0] = 0;
    dfs(g, 0);
    cout << cnt - 1 << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 256
use proconio::input;

// x ** n % mods を求める
pub fn mod_pow(x: i64, n: i64, mods: i64) -> i64 {
    if n == 0 {
        return 1;
    }
    let mut res = mod_pow(x * x % mods, n / 2, mods);
    if n % 2 == 1 {
        res = res * x % mods;
    }
    return res;
}

// (1/n) % mods を求める
pub fn mod_inv(n: i64, mods: i64) -> i64 {
    return mod_pow(n, mods-2, mods);
}

// nCk % mods を求める
pub fn mod_comb(n: i64, k: i64, mods: i64) -> i64 {
    let sum1 = (n-k+1..n+1).fold(1, |ac, x| ac * x % mods);
    let sum2 = (1..k+1).fold(1, |ac, x| ac * x % mods);
    return sum1 * mod_inv(sum2, mods) % mods;
}

// nCk の組み合わせを列挙する
pub fn combination(n: usize, k: usize) -> Vec<Vec<usize>> {
    let mut ans = Vec::new();
    if k == 1 {
        for i in 1..n+1 {
            let mut tmp = Vec::new();
            tmp.push(i);
            ans.push(tmp);
        }
    }
    else {
        for iter in combination(n-1, k-1) {
            let max = iter.iter().max().unwrap();
            for j in *max+1..n+1 {
                let mut tmp = iter.clone();
                tmp.push(j);
                ans.push(tmp);
            }
        }
    }
    ans
}


fn main() {
    input!{
        n: usize,
        a: [usize; n],
    }
    let mut ans = 0;
    let mut max = a[0];
    for iter in a {
        if iter > max {
            max = iter;
        }
        else if iter < max {
            ans += max - iter;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 5504
#include <cstdio>
typedef long long ll;

inline ll Lowbit(const ll x){return x&-x;}

int n,T[100005][2],Tn=1;
ll L,S;
char s[100005];

void DFS(int x,int d)
{
    for(int i=0;i<2;++i)
        if(!T[x][i])S^=Lowbit(L-d);
        else DFS(T[x][i],d+1);
}

int main()
{
    for(scanf("%d%lld",&n,&L);n--;)
    {
        scanf("%s",s);
        for(int i=0,p=1,c;s[i];p=T[p][c],++i)if(!T[p][c=s[i]&1])T[p][c]=++Tn;
    }
    DFS(1,0),puts(S?"Alice":"Bob");
    return 0;
}

Measured memory_bytes: 5760
using System;

class C
{
	static void Main()
	{
		var h = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
		long a = h[0], b = h[1], c = h[2], d = c - a - b;
		Console.WriteLine(d > 0 && 4 * a * b < d * d ? "Yes" : "No");
	}
}


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

int main()
{
  int N;
  int count=0;
  cin >> N;
  int s[N];
  for(int i=0;i<N;++i)
  {
    cin >> s[i];
  }
  for(int i=1;i<N;i++)
  {
    if (s[i]==s[i-1])
    {
      if(s[i] == s[i+1])
      {
        i++;
      }
      count++;
    }
  }
  cout << count << endl;
}


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

long long dp[3030][3030][2];

const long long MOD = 1000000007;

signed main() {
        int n, m;
        scanf("%d%d", &n, &m);
        dp[0][0][1] = 1;
        for (int x = 1; x <= n; x ++) dp[0][x][0] = 1;
        if (n == 1) { 
                dp[0][1][0] = 0;
                dp[0][1][1] = 1;
        }
        for (int t = 0; t < m; t ++) {
                for (int x = 0; x <= n; x ++) {
                        if (x == 0) {
                                (dp[t + 1][x][1] += dp[t][x][1]) %= MOD;
                                (dp[t + 1][x + 1][1] += dp[t][x][1]) %= MOD;
                        } else if (x == n) {
                                if (n != 1) {
                                        (dp[t + 1][x - 1][1] += dp[t][x][1]) %= MOD;
                                        (dp[t + 1][x - 1][0] += dp[t][x][0]) %= MOD;
                                        (dp[t + 1][x][1] += dp[t][x][1]) %= MOD;
                                        (dp[t + 1][x][0] += dp[t][x][0]) %= MOD;
                                } else {
                                        (dp[t + 1][x - 1][1] += dp[t][x][1] + dp[t][x][0]) %= MOD;
                                        (dp[t + 1][x][1] += dp[t][x][1]) %= MOD;
                                        (dp[t + 1][x][0] += dp[t][x][0]) %= MOD;
                                }
                        } else if (x == 1) {
                                (dp[t + 1][x - 1][1] += dp[t][x][1] + dp[t][x][0]) %= MOD;
                                (dp[t + 1][x][1] += 2 * dp[t][x][1] + dp[t][x][0]) %= MOD;
                                (dp[t + 1][x][0] += dp[t][x][0]) %= MOD;
                                (dp[t + 1][x + 1][1] += dp[t][x][1]) %= MOD;
                                (dp[t + 1][x + 1][0] += dp[t][x][0]) %= MOD;
                        } else {
                                (dp[t + 1][x - 1][1] += dp[t][x][1]) %= MOD;
                                (dp[t + 1][x - 1][0] += dp[t][x][0]) %= MOD;
                                (dp[t + 1][x][1] += 2 * dp[t][x][1]) %= MOD;
                                (dp[t + 1][x][0] += 2 * dp[t][x][0]) %= MOD;
                                (dp[t + 1][x + 1][1] += dp[t][x][1]) %= MOD;
                                (dp[t + 1][x + 1][0] += dp[t][x][0]) %= MOD;
                        }
                }
        }
        long long ans = 0;
        for (int x = 0; x <= n; x ++) (ans += dp[m][x][1]) %= MOD;
        printf("%lld\n", ans % MOD);
        return 0;
}


Measured memory_bytes: 143616
#include <stdio.h>
 
int p=0;
int q[2000001];
 
void chg(int a,int b){
  int x;
  x=q[a];
  q[a]=q[b];
  q[b]=x;
}
 
int max(int a,int b){
  if(q[a]>q[b]) return a;
  else return b;
}
 
int extract(){
  int r=q[1];
  int i;
  int x;
  int M;
  q[1]=q[p];
  p--;
  i=1;
  while(i*2 <= p ){
    if(i*2+1 <= p)
      M=max(i*2,i*2+1);
    else M=i*2;
    if(max(M,i)==M){chg(M,i);i=M;}
    else break;
 
  }
  return r;
}
 
 
 
void insert(int k){
  int x;
  int i,j;
  p++;
  q[p]=k;
  i=p;
  while(q[i]>q[i/2] && i>1){
    chg(i,i/2);
    i=i/2;
  }
}
 
int main(){
  char c[10];
  int i,j,k;
 
  while(1){
    scanf("%s",c);
 
    if(c[0]=='i'){
      scanf("%d",&k);
      insert(k);
    }
 
    if(c[0]=='e'){
 
      if(c[1]=='x')
    printf("%d\n",extract());
 
      if(c[1]=='n') break;
    }
  }
  return 0;
}



Measured memory_bytes: 5568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i, x) for (long long i = 0; i < x; i++)
#define repn(i, x) for (long long i = 1; i <= x; i++)
#define SORT(x) sort(x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define POSL(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())
#define POSU(x, v) (upper_bound(x.begin(), x.end(), v) - x.begin())
vector<pair<string, P> > vec;
// vector<vector<int>> data(3, vector<int>(4));

const string YES = "Yes";
const string NO = "No";

void solve(std::string S, std::string T) {
    bool flg = true;
    rep(i, S.length()) {
        if (S[i] != T[i]) flg = false;
    }
    if (flg)
        cout << YES << endl;
    else
        cout << NO << endl;
}

int main() {
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    solve(S, T);
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define EPS (1e-10)
using namespace std;

typedef complex<double> P; //Point
typedef pair<P,P> L; //Line, Segment


namespace std {
  bool operator < (const P& a, const P& b){
    return fabs(real(a)-real(b)) < EPS ? imag(a) < imag(b) : real(a) < real(b);
  }
  bool operator ==(const P& a, const P& b){
    return abs(a.real()-b.real())<EPS&&abs(a.imag()-b.imag())<EPS;
  }
}

double dot(P a, P b){ return real(conj(a)*b); }
double cross(P a, P b){ return imag(conj(a)*b); }

int ccw(P a, P b, P c){
  b -= a;
  c -= a;
  if(cross(b,c) > EPS) return 1;   // ????????????(b-a)????????´???????????????(c-a)????????¨?????????
  if(cross(b,c) < -EPS) return -1; // ????????????(b-a)????????´???????????????(c-a)????????¨?????????
  if(dot(b,c) < -EPS) return 2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

bool isIntersect(L s1, L s2){  
  //ccw ??????????????????????????¨, ????????????????????´?????????????????¨??????????????????????????????
  if(max(real(s1.first), real(s1.second)) + EPS < min(real(s2.first), real(s2.second)) ||
     max(imag(s1.first), imag(s1.second)) + EPS < min(imag(s2.first), imag(s2.second)) ||
     max(real(s2.first), real(s2.second)) + EPS < min(real(s1.first), real(s1.second)) ||
     max(imag(s2.first), imag(s2.second)) + EPS < min(imag(s1.first), imag(s1.second))) return false;

  return ( ccw(s1.first,s1.second,s2.first) * ccw(s1.first,s1.second,s2.second) <= 0 &&
           ccw(s2.first,s2.second,s1.first) * ccw(s2.first,s2.second,s1.second) <= 0 );
}

P crossPoint(L l, L m){
  double A = cross(l.second - l.first, m.second - m.first);
  double B = cross(l.second - l.first, l.second - m.first);
  if(fabs(A) < EPS && fabs(B) < EPS) return m.first;
  else if(fabs(A) >= EPS) return m.first + B / A * (m.second - m.first);
}

bool onEdge(P a){return a.real()==-100||a.real()==100||a.imag()==-100||a.imag()==100;}

int Unique(vector<P> &p){
  int res=0;
  for(int i=0;i<(int)p.size();i++){
    int flg=1;
    for(int j=i+1;j<(int)p.size();j++) if(p[i]==p[j]) flg=0;
    res+=flg;
  }  
  return res;
}

int main(){
  int n;
  while(cin>>n,n){
    int ans=1;
    vector<L> v;
    
    for(int i=0;i<n;i++){
      int sx,sy,gx,gy;
      cin>>sx>>sy>>gx>>gy;
      L l=L(P(sx,sy),P(gx,gy));
      
      vector<P> p;
      for(int i=0;i<v.size();i++){
	if(!isIntersect(l,v[i]))continue;
	P cp=crossPoint(l,v[i]);
	if(!onEdge(cp))p.push_back(cp);
      }
       ans+=1+Unique(p);
      v.push_back(l);
    }  
    cout<<ans<<endl;
  }
  return 0;
}

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

#define pb push_back
#define fi first
#define SZ(x) (int((x).size()))
#define se second
#define ll long long
#define pq priority_queue
#define MP make_pair
#define pii pair<int,int>
#define mod 998244353
#define debug(x) cerr<<#x<<"="<<x<<'\n'

const int maxn=4e5+10;

int n,m,c;
int a[maxn];
int pre[maxn],suf[maxn],f[maxn];

int main(){
	cin>>n>>m>>c;
	int cnt=0;
	for (int i=1;i<=n;i++) {
		char C;
		cin>>C;
		if (C=='o') a[i]=1,cnt++;
		else a[i]=0;
	}
	if (c==0) {
		if(cnt==m) {
			for (int i=1;i<=n;i++) {
				if (a[i]==1) printf("%d\n",i);
			}
		}
		return 0;
	}
	for (int i=1;i<=n;i++) {
		pre[i]=pre[i-1];
		if (a[i]==0) continue;
		if (i-c-1>=0) pre[i]=max(pre[i-c-1]+1,pre[i]);
		else pre[i]=max(pre[i],1);
	}
	for (int i=n;i>=1;i--) {
		suf[i]=suf[i+1];
		if (a[i]==0) continue;
		suf[i]=max(suf[i+c+1]+1,suf[i]);
	}
	for (int i=1;i<=n;i++) f[i]=pre[i]+suf[i+c+1];
	set <pii> s;
	for (int i=1;i<=n;i++) {
		int cur=max(pre[i-1],suf[i+1]);
		if (!s.empty()) cur=max(-(*s.begin()).fi,cur);
		if (cur<m) printf("%d\n",i);
		if (i>c) s.erase(MP(-f[i-c],i-c));
		s.insert(MP(-f[i],i));
	}
	return 0;
}


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

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

void paint(const vvi& g,int v,int d,int c,vi& ns,vi& res)
{
	queue<tuple<int,int>> q;
	q.emplace(v,d);
	while(q.size()){
		int cv,cd; tie(cv,cd)=q.front(); q.pop();
		if(ns[cv]>=cd)
			continue;
		if(ns[cv]==-1)
			res[cv]=c;
		ns[cv]=cd;
		if(cd==0)
			continue;
		for(int nv:g[cv])
			q.emplace(nv,cd-1);
	}
}

int main()
{
	for(int n,m;cin>>n>>m&&n|m;){
		vvi g(n);
		rep(i,m){
			int u,v; cin>>u>>v; u--,v--;
			g[u].push_back(v);
			g[v].push_back(u);
		}
		int q; cin>>q;
		vi vs(q),ds(q),cs(q);
		rep(i,q){
			cin>>vs[i]>>ds[i]>>cs[i];
			vs[i]--;
		}

		vi ns(n,-1),res(n);
		per(i,q)
			paint(g,vs[i],ds[i],cs[i],ns,res);

		rep(i,n) cout<<res[i]<<endl;
	}
}


Measured memory_bytes: 8952
import sys
sys.setrecursionlimit(10 ** 9)


input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = list(input())
    M = {'r': p, 's': r, 'p': s}

    ans = 0
    win = [False]*n
    for i in range(n):
        if win[i-k] and t[i-k] == t[i]:
            continue
        ans += M[t[i]]
        win[i] = True

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4724
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>

#define ll long long
#define ld long double
#define ull unsigned ll
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  Inf = 2 * 1000 * 1000 * 1000;
ll LINF = (ll)4e18;
using namespace std;
#define M_PI       3.14159265358979323846   // pi

const int nax = 2 * 1000 * 100 + 5;

int D[nax][2];

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			D[i][j] = 1e9;
		}
	}
	D[0][0] = s[0] != '.';
	D[0][1] = 1 - D[0][0];

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			D[i][1] = min(D[i][1], D[i - 1][j] + (s[i] != '#'));
			if (j != 1) {
				D[i][0] = min(D[i][0], D[i - 1][j] + (s[i] != '.'));
			}
		}
	}
	cout << min(D[n - 1][0], D[n - 1][1]);
 	return 0;
}

Measured memory_bytes: 2704
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
using ll = long long;
using P = pair<int,int>;

int main(void) {
  int r;
  cin >> r;

  cout << r*r << endl;
  return 0;
}
  

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

int n,m,a;
map<int,int>k;

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

Measured memory_bytes: 9600