akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int n, ans;
    cin >> n;   //nは偶数
    int m = n/2;
    int v[n];
    rep(i, n) {
        cin >> v[i];
    }
    int o[m], e[m];     //v[n]の奇数番目の項がo[m],偶数番目の項がe[m]
    for(int i = 0; i < n; i += 2) {
        o[i/2] = v[i];
    }
    for(int i = 1; i < n; i += 2) {
        e[(i-1)/2] = v[i];
    }

    sort(o, o+m);
    sort(e, e+m);

    int t1 = o[0];
    int k1 = 0;
    int count_o[m];
    for(int i = 0; i < m; i++) {
        count_o[i] = 0;
    }   

    for(int i = 0; i < m; i++) {
        if(t1 < o[i]) {
            t1 = o[i];
            k1++;
            count_o[k1]++;
        } 
        else {
            count_o[k1]++;
        }
    }

    int t2 = e[0];
    int k2 = 0;
    int count_e[m];
    for(int i = 0; i < m; i++) {
        count_e[i] = 0;
    } 

    for(int i = 0; i < m; i++) {
        if(t2 < e[i]) {
            t2 = e[i];
            k2++;
            count_e[k2]++;
        } 
        else {
            count_e[k2]++;
        }
    }

    sort(count_o, count_o + m);
    sort(count_e, count_e + m);

    int a1 = o[0];
    int b1 = 0;
    for(int i = 0; i < m; i++) {
        if(a1 < o[i]) {
            if(b1 == count_o[m-1]) {
                break;
            }
            a1 = o[i];
            b1 = 0;
        }
        b1++;
    }

    int a2 = e[0];
    int b2 = 0;
    for(int i = 0; i < m; i++) {
        if(a2 < e[i]) {
            if(b2 == count_e[m-1]) {
                break;
            }
            a2 = e[i];
            b2 = 0;
        }
        b2++;
    }

    if(a1 == a2) {
        int u = count_o[m-1] + count_e[m-2];
        int v = count_o[m-2] + count_e[m-1];
        ans = n - max(u, v);
    }
    else {
        ans = n - (count_o[m-1] + count_e[m-1]);
    }

    cout << ans;

    cout << endl;
    return 0;
}

Measured memory_bytes: 1408
from collections import*
n=input();G=[[]for d in[deque([1,n])]*-~n]
for C in[[0,1]+[0]*(n-2)+[2]]*~-n:a,b=map(int,raw_input().split());G[a]+=b,;G[b]+=a,
while d:
 v=d.popleft()
 for t in G[v]:
  if C[t]<1:C[t]=C[v];d+=t,
print["Snuke","Fennec"][n<2*C.count(1)]

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

int     main() {
        vector<int>     a(1000001, 0);
        int s;
        int i=1;
        cin >>s;
        while (true) {
                if (a.at(s)) break;
                else {
                        a.at(s)=i;
                        if (0==s%2) s /= 2;
                        else s += 2*s+1;
                        i++;
                }
        }
        cout << i << endl;
        return 0;
}

Measured memory_bytes: 4096
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;

int main(){
    int h,w;
    int flag = 0;
    char a[60][60];

    cin >> h >> w;
    FORQ(i,0,h+1){
        FORQ(j,0,w+1){
            a[i][j] = '.';
        }
    }
    FOR(i,0,h){
        FOR(j,0,w){
            cin >> a[i+1][j+1];
        }
    }
    FORQ(i,1,h){
        FORQ(j,1,w){
            if(a[i][j] == '#'){
                if(a[i-1][j] == '.' && a[i+1][j] == '.' && a[i][j-1] == '.' && a[i][j+1] == '.'){
                    flag = 1;
                }
            }
        }
    }
    if(flag == 0)cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 256
n, m = gets.strip.split(' ').map{|e|e.to_i}
str = '0' * n

hash = Hash.new()
m.times do
  s, c = gets.strip.split(' ')
  if hash.include?(s) and hash[s] != c
    puts '-1'
    exit
  else
    str[s.to_i - 1] = c
    hash.store(s, c)
  end
end

if str.size != 1 and str[0] == '0'
  if hash['1'] != '0'
    str[0] = '1'
  else
    puts '-1'
    exit
  end
end

puts str


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  int n,a,b;
  cin >> n >> a >> b;
  cout << min(a*n,b) << endl;
  return 0;
}


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

using namespace std;

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

    for (int i = 1; i <= n; ++i) {
        int tmp = count(a.begin(), a.end(), i);
        tmp += count(b.begin(), b.end(), i);
        cout << tmp << endl;
    }

    return 0;
}

Measured memory_bytes: 256
def minc(x, y, n, p)
	if p == Float::INFINITY
		a = []
		xn = x.each
		yn = y.each
		loop do
			a << (xn.next - yn.next).abs
		end
		a.max
	else
		sum = 0.0
		n.times do |i|
			sum += (x[i] - y[i]).abs ** p
		end
		sum ** (1.0 / p)
	end
end

n = gets.to_i
x = gets.split.map(&:to_f)
y = gets.split.map(&:to_f)

puts minc(x, y, n, 1).round(6)
puts minc(x, y, n, 2).round(6)
puts minc(x, y, n, 3).round(6)
puts minc(x, y, n, Float::INFINITY).round(6)

Measured memory_bytes: 8960
// ABC 153-E
// 2020.1.26 bal4u

#include <stdio.h>
#include <string.h>

#define gc() getchar_unlocked()

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

int N;
int dp[30005];

int main()
{
	int i, H, ans;
	
	H = in(), N = in();
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	while (N--) {
		int A = in(), B = in();
		for (i = 0; i <= H; ++i) if (dp[i] >= 0) {
			if (dp[i+A] < 0 || dp[i] + B < dp[i+A]) dp[i+A] = dp[i] + B;
		}
	}
	ans = 0x5fffffff;
	for (i = H; i <= H+10000; ++i) if (dp[i] >= 0 && dp[i] < ans) ans = dp[i];
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(input())
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):
   P[i+1][1:-1]=map(int,input().split())
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()


Measured memory_bytes: 5724
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
int x[10], y[10];

double dist(int i, int j) {
  double dx = x[i] - x[j];
  double dy = y[i] - y[j];
  return pow(dx * dx + dy * dy, 0.5);
}

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

  cin >> n;
  REP(i, n) cin >> x[i] >> y[i];

  vector<int> v(n);
  REP(i, n) v[i] = i;

  double sum = 0.0;
  do {
    REP(i, n - 1) sum += dist(v[i], v[i + 1]);
  } while(next_permutation(v.begin(), v.end()));

  int fa = 1;
  FOR(i, 2, n + 1) fa *= i;

  cout << fixed << setprecision(10) << sum / fa << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace B
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var nk = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var hi = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(hi.Count(x => x >= nk[1]));
        }
    }
}


Measured memory_bytes: 19168
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int a,b;
    cin>>a>>b;
    if(a==b){
        cout<<a*2<<endl;
        return 0;
    }
    int c=max(a,b);
    c=c*2-1;
    cout<<c<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm> 
#include <math.h>
#include <queue>
#include <functional>
#include <map>
#include <vector>
#include <string>
using namespace std;

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

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



int main(void) {
	ll mi = INF, n;
	cin >> n;
	for (int i = 0; i < 5; i++) {
		ll a; cin >> a;
		mi = min(mi, a);
	}

	cout << 5 + max((n + mi - 1) / mi - 1, (ll)0) << endl;

}


Measured memory_bytes: 256
N = int(input())
F = [list(map(int,input().split())) for i in range(N)]
P = [list(map(int,input().split())) for i in range(N)]

ans = -float('inf')
for b in range(1,2**10):
    tmp = 0
    for i in range(N):
        c = 0
        for k in range(10):
            if b&(1<<k) and F[i][k]:
                c += 1
        tmp += P[i][c]
    ans = max(ans,tmp)
print(ans)


Measured memory_bytes: 3064
import sys

A,B = map(int, input().split())
S = input()

str_len = len(S)

for i in range(str_len):

    a = S[i]
    if i==A:
        if a=="-":
            continue
        else:
            print("No")
            sys.exit()
    if str.isdecimal(a)==False:
        print("No")
        sys.exit()
print("Yes")


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll n,k,s;
  cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
    int mn=v[0];
    int c=1;
  for(int i=1;i<n;i++)
  {
      if(v[i]<=mn)
      {
          c++;
          mn=v[i];
      }
  }
  cout<<c<<endl;
  return 0;
}


Measured memory_bytes: 1152
using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{    

    class Node
    {
        public int? key = null;
        public Node left;
        public Node right;
    }

    class Program
    {       
        static Node root;
        static Node u;

        static void Insert(int k)
        {
            u = new Node();
            u = root;

            while(true)
            {
                if(k < u.key)
                {
                    if(u.left == null)
                    {
                        Node newnode = new Node();
                        u.left = newnode;
                        newnode.key = k;
                        break;
                    }
                    else
                    {
                        u = u.left;
                    }                 
                }
                else if(k > u.key)
                {
                    if(u.right == null)
                    {
                        Node newnode = new Node();
                        u.right = newnode;
                        newnode.key = k;
                        break;
                    }
                    else
                    {
                        u = u.right;
                    }                  
                }
            }          
            return;
        }

        static void Pre(Node u)
        {
            if(u == null)
            {
                return;
            }
            Console.Write(" " + u.key);
            Pre(u.left);
            Pre(u.right);
        }

        static void Ino(Node u)
        {
            if(u == null)
            {
                return;
            }
            Ino(u.left);
            Console.Write(" " + u.key);
            Ino(u.right);
        }
        
        
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] input;
            string order;
            int key;

            for(int i = 0; i < n; i++)
            {
                input = Console.ReadLine().Split(' ');
                order = input[0];

                if(order == "insert")
                {
                    key = int.Parse(input[1]);
                    if(i == 0)
                    {
                        root = new Node();
                        root.key = key;
                        root.left = null;
                        root.right = null;
                    }
                    else
                    {
                        Insert(key);
                    }                 
                }
                else if(order == "print")
                {
                    Ino(root);
                    Console.WriteLine();
                    Pre(root);
                    Console.WriteLine();
                }
            }
        }
    }
}



Measured memory_bytes: 39960
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
	// a-z 97-122
	// A-Z 65-90
	// a-A 32
	
	char ch;
	scanf("%c", &ch);
	while (ch != '\n')
	{
		if ( ch >= 97 && ch <= 122)
		{
			ch = (char)(ch - 32);
		}
		else if (ch >= 65 && ch <= 90)
		{
			ch = (char)(ch + 32);
		}
		printf("%c", ch);
		scanf("%c", &ch);
	}
	cout << endl;
	return 0;
} 

Measured memory_bytes: 3136
#include <iostream>
#include <cstdio>
using namespace std;
int main(void){
    
    int i, x;
    
    for(i = 1; i <= 10000; i++){
        cin >> x;
            if(x == 0){
                break;
            }
        cout << "Case " << i << ": " << x << endl;
    }
    return 0;
}



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

#define CIN2(a,b) long long a,b;cin >> a >> b;
#define CIN3(a,b,c) long long a,b,c;cin >> a >> b >> c;

int main(){
    CIN3(a,b,c)
    string ans = ((a<c&&c<b)||(a>c&&c>b))?"Yes":"No";
    cout << ans << endl;
}


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

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//grobal variable
//------------------------------------------
int N,M;
VI Vec;

//動的計画法で役に立つ関数
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; }

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

ll lcm(ll a, ll b) {
  ll g = gcd(a, b);
  return a/g*b;
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int A, B, C, D; cin >> A >> B >> C >> D;

    if (A<=C)
    {
        if (B<=D)
        {
            cout << max(0, B-C) << endl;
        }
        else
        {
            cout << max(0,D-C) << endl;
        }
    }
    else
    {
        if (B<=D)
        {
            cout << max(0,B-A) << endl;
        }
        else
        {
            cout << max(0,D-A) << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout<< dest << (sizeof...(Args)?" ":""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define out(...) _OUTPUT_IMPL_(__VA_ARGS__)
//小さい方に寄る
#define space_op(x, y, a, b, c) ([](auto x_, auto y_, auto a_, auto b_, auto c_){if(x_<y_)return a_;if(x_>y_)return c_;return b_;}(x,y,a,b,c))

int main() {
	in(int, a, b);
	(a += 11) %= 13;
	(b += 11) %= 13;
	out(space_op(a, b, "Bob", "Draw", "Alice"));
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[m][2];
        for (int i=0; i<m; i++) {
            arr[i][0] = sc.nextInt() - 1;
            arr[i][1] = sc.nextInt() - 1;
        }

        UnionFind uf = new UnionFind(n);
        for (int i=0; i<m; i++) {
            uf.unite1(arr[i][0], arr[i][1]);
        }

        Set<Integer> set = new HashSet<>();
        for (int i=0; i<n; i++) {
//            System.out.println(uf.parent[i]);
            set.add(uf.find(i));
        }

//        System.out.println(set);
        System.out.println(set.size() - 1);

    }

    class UnionFind {

        int[] parent, rank, size;

        void init(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i=0; i<n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i=0; i<n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x==parent[x]) return x;
            return parent[x] = find(parent[x]);
        }

        //    結合して木のサイズを更新
        public void unite1(int x, int y) {
            x = find(x);
            y = find(y);
            if (x==y) return;
            parent[y] = x;
        }

        //    結合して木の深さを更新
        public void unite2(int x, int y) {
            x = find(x);
            y = find(y);
            if (x==y) return;
            if (rank[x] < rank[y]) {
                parent[x] = parent[y];
            } else {
                parent[y] = parent[x];
                if (rank[x]==rank[y]) rank[x]++;
            }
        }

        public boolean same(int x, int y) {
            return find(x) == find(y);
        }

        public int size(int x) {
            return size[find(x)];
        }


    }


}



Measured memory_bytes: 62208
#include <bits/stdc++.h>
#include <atcoder/all>

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

using namespace std;
using namespace atcoder;
using ll = long long;

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

    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    rep(i, n) cin >> a.at(i);
    rep(i, m) cin >> b.at(i);

    vector<ll> c = convolution(a, b);
    rep(i, n + m - 1) {
        printf("%lld", c.at(i));
        printf(i != n + m - 2 ? " " : "\n");
    }
    
    return 0;
}

Measured memory_bytes: 27216
# D - Summer Vacation ★
from collections import defaultdict
from heapq import heappush, heappop

_input = list(map(int, input().split()))
n = _input[0]
m = _input[1]
jobs = defaultdict(list)

# かかる日数ごとに報酬をまとめる
for i in range(n):
    a, b = list(map(int, input().split()))
    if a <= m:
        jobs[a].append(b)

# M-1日目、M-2日目…と後ろから順に得られる報酬が多い仕事を割り振っていく
# ※日数制限があったほうが埋めやすいので
reward = 0
heapsort = []
for daysLeft in range(1, m + 1):
    if daysLeft in jobs:
        for b in jobs[daysLeft]:
            heappush(heapsort, -b)
    if len(heapsort) > 0:
        reward += -heappop(heapsort)
print(reward)

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

int main(){
	string s, s1, s2;
	cin >> s;
	s1 = s.substr(0, 2);
	s2 = s.substr(2, 2);
	//cout << s1 << s2 << endl;
	if((s1 == "00" || s1 > "12") && (s2 == "00" || s2 > "12")){
		cout << "NA" << endl;
		return 0;
	}
	if(s1 == "00" || s1 > "12"){
		cout << "YYMM" << endl;
		return 0;
	}
	if(s2 == "00" || s2 > "12"){
		cout << "MMYY" << endl;
		return 0;
	}
	cout << "AMBIGUOUS" << endl;
	return 0;

}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#define rep(i,j,n) for(i=j;i<(n);i++)
#define rrep(i,j,n) for(i=j;i>(n);i--)

using namespace std;

int main(){
    string s;
    int ans=0;
    int i;
    cin>>s;
    rep(i,1,s.size()){
        if(s[i-1]!=s[i]){
            ans++;
        }
    }
    cout<<ans<<endl;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll L; int N; cin >> L >> N;
    vector<vector<ll>> sum0(N,vector<ll>(2)),sum1(N,vector<ll>(2));
    for (int i=0;i<N;++i){
        cin >> sum0[i][0];
        sum0[N-1-i][1]=L-sum0[i][0];
    }
    sum1[0][0]=sum0[0][0]*2,sum1[0][1]=sum0[0][1]*2;
    for (int i=0;i<N-1;++i)
        for (int j=0;j<2;++j)
            sum1[i+1][j]=sum1[i][j]+sum0[i+1][j]*2;
    ll ans=max(L-sum0[0][0],L-sum0[0][1]);
    for (int j=0;j<2;++j){
        for (int i=0;i<N-1;++i){
            int pos=(N-1-i)/2,neg=(N-i)/2;
            ll cnt=0;
            cnt+=sum1[neg-1][j^1];
            cnt+=sum1[i+pos][j]-sum1[i][j]-sum0[i][j]*2*pos;
            if ((N-1-i)&1){
                cnt-=sum0[neg-1][j^1];
                cnt+=sum0[i][j]*2*(pos+1);
            } else {
                cnt-=sum0[i+pos][j];
                cnt+=sum0[i][j]*2*(pos+1);
            }
            ans=max(ans,cnt);
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 22144
#!/usr/bin/env python3
import sys
from itertools import chain


def solve(K: int, S: str):
    if len(S) <= K:
        return S
    else:
        return S[:K] + "..."


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    K = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    answer = solve(K, S)
    print(answer)


if __name__ == "__main__":
    main()


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

int main(){
  long a;
  long double b;
  cin >> a >> b;
  ll c = a*b;
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 3732
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 100000000;//10^8
ll MOD  = 1000000007;
ll XOR(ll x){
    if(x <= 0) return 0;
    ll ans;
    if(x % 2 == 1){
        ans = (x+1) / 2 % 2;
    }
    else{
        ans = (x+1) / 2 % 2 + x;
    }
    return ans;
}
int main(void){
    ll A,B;
    cin >> A >> B;
    ll a = XOR(A-1);
    ll b = XOR(B);
    vector<bool> A_(50);
    vector<bool> B_(50);
    vector<bool> ans(50);
    ll Answer = 0;
    for(int i = 0; i < 50; i++){
        A_.at(i) = a % 2;
        a /= 2;
        B_.at(i) = b % 2;
        b /= 2;
        ans.at(i) = ( A_.at(i) + B_.at(i) ) % 2;
        Answer += ans.at(i) * pow(2, i);
    }
    cout << Answer << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
char s[100001],ch[100001];
int vis[100001];
int main() {
	scanf("%s",s);
	int len=strlen(s);
	int nowt=0;
	for (int i=0;i<len;i++) {
		if (s[i]!='x') ch[++nowt]=s[i];
			else vis[nowt]++;
	}
	for (int i=1;i<=nowt;i++)
		if (ch[i]!=ch[nowt+1-i]) {
			printf("-1\n");
			return 0;
		}
	int ans=0;
	for (int i=0;i<=(nowt-1)/2;i++) ans+=abs(vis[i]-vis[nowt-i]);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];

    int vx[] = {0, 1, 0, -1};
    int vy[] = {1, 0, -1, 0};
    rep(y, h)rep(x, w){
        if(s[y][x] == '.') continue;
        bool f = 0;
        rep(i, 4){
            int nx = x+vx[i], ny = y+vy[i];
            if(nx < 0 || ny < 0 || w <= nx || h <= ny) continue;
            if(s[ny][nx] == '#') f = 1;
        }
        if(!f){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


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

using ll=long long; 

void solve(){
	int n;
	cin>>n;
	int a,b;
	cin>>a>>b;
	string s;
	cin>>s;
	int abcnt=0;
	int bcnt=0;
	for(int i=0; i<n; i++){
		if(s[i]=='a'){
			if(abcnt<a+b){
				cout<<"Yes"<<endl;
				abcnt++;
			}else{
				cout<<"No"<<endl;
			}
		}
		else if(s[i]=='b'){
			if(abcnt<a+b&&bcnt<b){
				cout<<"Yes"<<endl;
				abcnt++;
				bcnt++;
			}else{
				cout<<"No"<<endl;
			}
		}
		else{
			cout<<"No"<<endl;
		}
	}
}

signed main(){
	//while(1)
	solve();
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a, b) for(int i = a; i < b; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int n; cin>>n;
    string s; cin>>s;
    
    if(n==1||n%2!=0){
        cout<<"No"<<endl;
        return 0;
    }
    if(s.substr(0,s.size()/2)==s.substr(s.size()/2,s.size()/2)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef long long ll;
typedef complex<double> CP;
typedef pair<ll,int> P;
static const int INF=1<<24;

int main(){
	string s,st[10];
	st[1]="0";
	st[2]="00";
	st[3]="000";
	st[4]="0000";
	st[5]="00000";
	int l;
	while(cin>>s>>l,l){
		vector<P> a;
		//cout<<s.size()<<" "<<l<<endl;
		P tmp;
		stringstream ss1;
		ss1<<s;
		ss1>>tmp.F;
		tmp.S=0;
		a.PB(tmp);
		if(l-s.size()>0){
			s+=st[l-s.size()];
		}
		//cout<<s<<endl;
		
		rep(i,30){
			bool f=false;
			stringstream s1,s2,s3;
			int t1,t2;
			sort(ALL(s));
			s1<<s;
			s1>>t1;
			sort(ALL(s),greater<char>());
			s2<<s;
			s2>>t2;
			rep(j,a.size()){
				if(a[j].F==t2-t1){
					f=true;
					cout<<a[j].S<<" "<<t2-t1<<" "<<i+1-a[j].S<<endl;
				}
			}
			if(f) break;
			P tmp;
			tmp.F=t2-t1;
			tmp.S=i+1;
			a.PB(tmp);
			s3<<t2-t1;
			s3>>s;
			if(l-s.size()>0){
				s+=st[l-s.size()];
			}
			//cout<<s<<" "<<t2<<" "<<t1<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1264
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
using namespace std;
typedef long long ll;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))

void solve()
{
    ll N,A,B;
    cin >> N >> A >> B;
    ll ans = min(B,A*N);
    cout << ans << endl;
}

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


Measured memory_bytes: 256
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        cnt+=j%9
        j//=9
    ans = min(ans,cnt)
print(ans)

Measured memory_bytes: 40940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define out(a) cout<<fixed<<setprecision((a))
 

int main(){ 
	ll r,D,x;
	cin >> r >> D >> x;
	FOR(i,1,11){
		x = r*x-D;
		cout << x << endl;
	}
}


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

using namespace std;

int main(){
  int N;
  cin >> N;
  vector<pair<double, string>> v;
  v.reserve(10);
  for(int i = 0; i < N; ++i)
  {
    double x;
    string u;
    cin >> x >> u;
    pair<double, string> p(x,u);
    v.push_back(p);
  }
  double sum = 0;
  for(auto p: v)
  {
    if(p.second == "JPY")
    {
      sum += p.first;
    }
    else
    {
      sum += p.first * 380000;
    }
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<bitset>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<iomanip>
#include <functional>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const double EPS = 1e-10;
const int INF = 2147483647;
//cout << fixed << std::setprecision(9)
//memset(a, 0, sizeof(a));
//--------------------------

vector<int> a, b, c;
int n;

int main()
{
	cin >> n;

	for (int i = 0;i < n;i++) {
		int t;
		cin >> t;
		a.push_back(t);
	}

	for (int i = 0;i < n;i++) {
		int t;
		cin >> t;
		b.push_back(t);
	}

	for (int i = 0;i < n;i++) {
		int t;
		cin >> t;
		c.push_back(t);
	}

	sort(a.begin(), a.end());
	sort(c.begin(), c.end());

	ll ans = 0;
	vector<int>::iterator itr1,itr2;

	for (int i = 0;i < n;i++) {
		int k = b[i];

		itr1 = lower_bound(a.begin(), a.end(), k);
		itr2 = upper_bound(c.begin(), c.end(), k);

		ll aa;
		ll cc;

		if (itr1 == a.end()) {
			aa = (ll)n;
		}
		else {
			aa = (ll) (itr1 - a.begin());
		}

		if (itr2 == c.end()) {
			cc = (ll)n;
		}
		else {
			cc = (ll) (itr2 - c.begin());
		}

		ans += aa * (n - cc);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1784
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;



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

	int m = BIG_NUM;
	for (int i = 0; i < n - 1; i++) {
		int s1 = 0;
		for (int j = 0; j <= i; j++) {
			s1 += w[j];
		}
		int s2 = 0;
		for (int j = i + 1; j < n; j++) {
			s2 += w[j];
		}
		m = min(m, abs(s1 - s2));

	}
	cout << m << endl;
}


Measured memory_bytes: 3608
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    cout << (A-1)*(B-1) << endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static final int MOD = 1000000007;

    long[] fac, finv, inv;

    void init(int MAX){
        fac  = new long[MAX];
        finv = new long[MAX];
        inv  = new long[MAX];

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

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

    public Main(){

        Scanner scanner = new Scanner(System.in);
        int X1, X2, Y1, Y2;
        X1 = scanner.nextInt();
        Y1 = scanner.nextInt();
        X2 = scanner.nextInt();
        Y2 = scanner.nextInt();

        init(X2+Y2+3);

        long R = COM(X2+Y2+2, X2+1);
        R = (R - COM(X1+Y2+1, X1)%MOD) % MOD;
        if(R<0) R += MOD;
        R = (R - COM(X2+Y1+1, Y1)%MOD) % MOD;
        if(R<0) R += MOD;
        R = (R + COM(X1+Y1, X1)) % MOD;
        
        System.out.println(R);
    }

    public static void main(String args[]) throws Exception{
        Main main = new Main();
    }
}


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

using namespace std;

int main() {
  int n, m, q;
  scanf("%d %d %d", &n, &m, &q);
  vector<vector<int>> trains(n, vector<int>(n + 1, 0));

  int l, r;
  for (int i = 0; i < m; ++i) {
    scanf("%d %d", &l, &r);
    trains[--l][--r]++;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = n - 1; 0 < j; --j) {
      trains[j - 1][i] += trains[j][i];
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= n; ++j) {
      trains[i][j] += trains[i][j - 1];
    }
  }

  int p, t;
  for (int i = 0; i < q; ++i) {
    scanf("%d %d", &p, &t);
    printf("%d\n", trains[--p][--t]);
  }
}


Measured memory_bytes: 1920
#include<stdio.h>
int main(void)
{
    long int n,a[100],max,min,i,s,tmp;
    scanf("%ld",&n);
    for(i=0;i<n;i++)
        scanf("%ld",&a[i]);
    max=a[0]; min=a[1];
    for(i=0;i<n;i++){
        if(max<a[i]){
            tmp=max; max=a[i]; a[i]=tmp;
        }
        if(min>a[i]){
            tmp=min; min=a[i]; a[i]=tmp;
        }
    }
    s=max-min;
    printf("%ld\n",s);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

ll n;
ll kp;
vector<ll> a(1000000);
vector<ll> f(1000000);

bool isok(ll ai, ll fi, ll x){
    ll v = ai*fi;
    if(v <= x)return true;
    else {
        ll shugyo = (v-x)/fi + min((ll)1,(v-x)%fi);
        if(shugyo > kp)return false;

        kp -= shugyo;
    }
    return true;   
}

int main(){
    ll n, k;
    cin >> n >> kp;
    vector<ll> a(n), f(n);
    ll sum = 0;
    rep(i, n){
        cin >> a[i];
        sum += a[i];
    }
    rep(i, n)cin >> f[i];
    if(sum <= kp){
        cout << 0;
        return 0;
    }
    sort(a.begin(), a.begin()+n);
    sort(f.begin(), f.begin()+n, greater<ll>());

    ll r = a[n-1]*f.front();
    ll l = 0;
    ll base = kp;
    // rep(i, n)cout << a[i] << ",";cout << endl;
    // rep(i, n)cout << f[i] << ",";cout << endl;
    while(r>=l){
        kp = base;
        bool flg = true;
        ll mid = l+(r-l)/2;
        rep(i, n)if(!isok(a[i], f[i], mid)){
            flg = false;
            break;
        }
        if(flg)r = mid-1;
        else l = mid+1;
    }
    cout << l << endl;
}

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

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

signed main(){

  int n,q;
  cin>>n>>q;
  string s;
  cin>>s;
  using pii = pair<int,int>;
  vector<pii> queries(q);
  for(auto& q:queries)cin>>q.first>>q.second;

  vector<int> sum(n+1);
  rep(i,n-1){
    if(s[i]=='A'&&s[i+1]=='C')sum[i+1]++;
  }
  rep(i,n)sum[i+1]+=sum[i];
  //for(auto x:sum)cout<<x<<" ";cout<<endl;
  for(auto q:queries){
    cout<<sum[q.second-1]-sum[q.first-1]<<endl;
  }

}

Measured memory_bytes: 2176
'''
研究室PCでの解答
'''
import math
#import numpy as np
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 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    l = int(ipt())
    if l <= 60:
        print(2,l)
        for i in range(l):
            print(1,2,i)
        exit()
    else:
        l2 = format(l,'b')
        n = len(l2)
        ans = []
        for i in range(n-1):
            ans.append((i+1,i+2,0))
            ans.append((i+1,i+2,2**i))
        nii = 2**(n-1)
        for i in range(1,n):
            if (l>>(n-1-i))&1:
                ans.append((n-i,n,nii))
                nii += 2**(n-i-1)
        print(n,len(ans))
        for a,b,c in ans:
            print(a,b,c)
    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 75000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))


int main(){
	ll a,b;
	cin >> a;
	cout << a*a << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int H,W;
  cin>>H>>W;
  vector<vector<char>>A(H,vector<char>(W));
  for(int i=0;i<H;i++){
  string s;
    cin>>s;
    for(int j=0;j<W;j++)
       A[i][j]=s.at(j);
  }vector<vector<int>>dp(H,vector<int>(W));
  if(A[0][0]=='.')
    dp[0][0]=0;
  else
    dp[0][0]=1;
  for(int i=1;i<H;i++){
  if(A[i][0]=='.')
    dp[i][0]=dp[i-1][0];
    else{
    if(A[i-1][0]=='#')
      dp[i][0]=dp[i-1][0];
      else
        dp[i][0]=dp[i-1][0]+1;
    }
  }for(int j=1;j<W;j++){
  if(A[0][j]=='.')
    dp[0][j]=dp[0][j-1];
    else{
    if(A[0][j-1]=='#')
      dp[0][j]=dp[0][j-1];
      else
        dp[0][j]=dp[0][j-1]+1;
    }
  }for(int i=1;i<H;i++){
   for(int j=1;j<W;j++){
   if(A[i][j]=='.')
     dp[i][j]=min(dp[i-1][j],dp[i][j-1]);
     else{
     int a=dp[i-1][j]; int b=dp[i][j-1];
       if(A[i-1][j]=='.')
         a++;
       if(A[i][j-1]=='.')
         b++;
     dp[i][j]=min(a,b);
     
     }
     
   }
  }int ans=dp[H-1][W-1];
  cout<<ans<<endl;
   return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = ~(1<<31);
const int MOD = 1e9+7;
const double EPS = 1.0e-10;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main(){
	int n,k;
	cin >> n >> k;
	int r,s,p;
	cin >> r >> s >> p;
	string t;
	cin >> t;

	int ans = 0,flag[n*2+10] = {};
	for(int i = 0; i < n; i++){
		if(!flag[i]){
			switch(t[i]){
				case 'r': ans += p; break;
				case 's': ans += r; break;
				case 'p': ans += s; break;
			}
			if(i+k<n && t[i] == t[i+k]) flag[i+k] = 1;
		}
	}
	cout << ans << endl;
	
	return 0;
}


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

#define debug(x) cout<<#x<<": "<<x<<endl
#define rep(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef long long ll;


void solve() {
#ifdef _WIN32
	istream &cin = ifstream("input.txt");
#endif
	ll n, m;
	cin >> n >> m;

	vector<ll> v(100000);
	rep(i, n) {
		ll x, y;
		cin >> x >> y;
		v[--x] += y;
	}
	ll sum = 0;
	rep(i, 100000) {
		sum += v[i];
		if (sum >= m) {
			cout << i + 1 << endl;
			break;
		}
	}
}



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

	solve();
#ifdef _WIN32
	system("PAUSE");
#endif
	return 0;
}

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

int H, W;
char grid[110][110];

void chmin(int& a, int b) {
  if (a > b) a = b;
}
int main() {
  cin >> H >> W;

  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      cin >> grid[i][j];
    }
  }
  
  int dp[110][110];
  
  
  for (int i = 0; i <= H; i++) {
    for (int j = 0; j <= W; j++) {
      dp[i][j] = 10010;
    }
  }
  
  if (grid[1][1] == '#') {
    dp[1][1] = 1;
  } else {
    dp[1][1] = 0;
  }
  
  for (int i = 1; i <= H; i++) {
    if (grid[i][1] == '.' && grid[i+1][1] == '#') {
      chmin(dp[i+1][1], dp[i][1] + 1);
    } else {
      chmin(dp[i+1][1], dp[i][1]);
    }                          
  }
  

  
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (grid[i][j] == '.' && grid[i][j+1] == '#') {
        chmin(dp[i][j+1], dp[i][j] + 1);
      } else {
        chmin(dp[i][j+1], dp[i][j]);
      }
      
      if (grid[i-1][j+1] == '.' && grid[i][j+1] == '#') {
        chmin(dp[i][j+1], dp[i-1][j+1] + 1);
      } else {
        chmin(dp[i][j+1], dp[i-1][j+1]);
      }
    }
  }
  

  
  
  cout << dp[H][W] << endl;
}

Measured memory_bytes: 3608
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N, C, K = map(int, input().split())
    T = [int(input()) for _ in range(N)]
    T.sort()
    answer = 0
    cst = C
    time = 0
    for t in T:
        if (time + K >= t) and (cst + 1 <= C):
            cst += 1
        else:
            answer += 1
            time = t
            cst = 1

    print(answer)


if __name__ == "__main__":
    main()


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

int main() {
    string s, ans = "Yes";
    cin >> s;
    for(int i= 0; i < s.size(); ++i) {
        if(i%2 == 0) {
            if(s[i] == 'L') {
                ans = "No";
                break;
            }
        } else {
            if(s[i] == 'R') {
                ans = "No";
                break;
            }
        }
    }
    cout << ans << '\n';
}

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

typedef struct{
	long num;
	long t;
}team;

team a[1000000];
long n, b[1000000];

int main(){
	while(1){
		
		scanf(" %ld", &n);
		if(n==0) break;
		
		for(int i=0; i<n; ++i){
			a[i].t=0;
			scanf(" %ld", &a[i].num);
			for(int j=0; j<4; ++j){
				int p, q;
				scanf(" %d %d", &p, &q);
				a[i].t+=p*60+q;
			}
			b[i]=a[i].t;
		}
		
		sort(b, b+n);
		long c[3];
		c[0]=b[0]; c[1]=b[1]; c[2]=b[n-2];
		
		for(int i=0; i<3; ++i){
			for(long j=0; j<n; ++j){
				if(c[i]==a[j].t) printf("%ld\n", a[j].num);
			}
		}
		
	}
	return 0;
}
		

Measured memory_bytes: 3288