akhauriyash/Code-Regression huggingface dataset:
N,M = map(int,input().split())
xyz = []
for i in range(N):
    xyz.append(list(map(int,input().split())))

ans = 0
for k in range(8):
    l = []
    if k == 0:
        for i in range(N):
            l.append(xyz[i][0] + xyz[i][1] + xyz[i][2])
    elif k == 1:
        for i in range(N):
            l.append(xyz[i][0] + xyz[i][1] - xyz[i][2])
    elif k == 2:
        for i in range(N):
            l.append(xyz[i][0] - xyz[i][1] + xyz[i][2])
    elif k == 3:
        for i in range(N):
            l.append(-xyz[i][0] + xyz[i][1] + xyz[i][2])
    elif k == 4:
        for i in range(N):
            l.append(xyz[i][0] - xyz[i][1] - xyz[i][2])
    elif k == 5:
        for i in range(N):
            l.append(-xyz[i][0] + xyz[i][1] - xyz[i][2])
    elif k == 6:
        for i in range(N):
            l.append(-xyz[i][0] - xyz[i][1] + xyz[i][2])
    elif k == 7:
        for i in range(N):
            l.append(-xyz[i][0] - xyz[i][1] - xyz[i][2])

    l = sorted(l)
    t = 0
    for i in range(1,M+1):
        t += l[-i]
    ans = max(ans , t)
print(ans)


Measured memory_bytes: 39892
import sys

import math
import itertools


n=int(input())
alp=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
ans=[]
while True:
    b=False
    if(n%26==0):
        b=True
    ans.append(alp[n%26-1])
    if(b):
        n-=1
    n//=26
    if(n==0):
        break
ans.reverse()
print(''.join(ans))

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<bool>> vvb;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

template <typename T>
void fin(T a)
{
  cout << a << endl;
  exit(0);
}

//実行部
void Main()
{
  ll n; cin >> n;
  map <char, ll> ans;
  rep(i, n)
  {
    str s; cin >> s;
    if(!ans.count(s[0])) ans[s[0]] = 1; else ans[s[0]]++;
  }
  vll a(5);
  a[0] = ans['M'];
  a[1] = ans['A'];
  a[2] = ans['R'];
  a[3] = ans['C'];
  a[4] = ans['H'];
  ll A = 0;
  for(ll i = 0;i < 5;i++)
  {
    for(ll j = i + 1;j < 5;j++)
    {
      for(ll k = j + 1;k < 5;k++)
      {
        A += a[i] * a[j] * a[k];
      }
    }
  }
  fin(A);
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=sc.nextInt();
		}
		
		
		int ans = selectionSort(arr);
		
		for(int i=0;i<arr.length;i++)
		{
			if(i==arr.length-1)
			{
				System.out.print(arr[i]);
			}
			else
			{
				System.out.print(arr[i]+" ");
			}
		}
		System.out.println();
		
		System.out.println(ans);
		
	}
	
	
	public static int selectionSort(int[] arr)
	{
		
		int count=0;
		for(int i=0;i<arr.length;i++)
		{
			int min = i;
			//找到最小的那个
			for(int j=i;j<arr.length;j++)
			{
				if(arr[j]<arr[min])
				{
					min = j;
				}
			}
			
			//换  把最小的放到现在这个位置
			int temp = arr[i];
			arr[i]=arr[min];
			arr[min]=temp;
			
			if(i!=min)
			{
				count++;
			}

		}
		
		return count;
	}
}



Measured memory_bytes: 26280
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    cout << A * B << endl;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2000,mod=1e9+7;
inline int powmod(int a,int b){int c=1;while(b){if(b&1)c=(LL)c*a%mod;a=(LL)a*a%mod;b>>=1;}return c;}
int n,k,f[N],g[N],num,ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i*i<=n;i++)if(n%i==0)
	{
		f[++num]=i;
		if(i*i!=n)f[++num]=n/i;
	}
	sort(f+1,f+num+1);
	for(int i=1;i<=num;i++)
	{
		g[i]=powmod(k,(f[i]+1)/2);
		for(int j=1;j<i;j++)if(f[i]%f[j]==0)g[i]=(g[i]-g[j]+mod)%mod;
		ans=(ans+(LL)g[i]*((f[i]&1)?f[i]:f[i]/2)%mod)%mod;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

ll gcd(ll a, ll b){return !b ? a : gcd(b, a % b);}
ll modP(ll a, ll b) {return (!b ? 1 : (modP(a, b / 2) * modP(a, b / 2) * (b % 2 ? a : 1)) % MOD);}

ll n, m, W, dp[maxN * maxN], w[maxN], v[maxN];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> W;
	for (int i = 0; i < n; i++){
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i < n; i++){
		for (int j = W; j > -1; j--){
			if (j == 0 || j < w[i]) continue;
			dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
		}
	}
	cout << dp[W];
	return 0;
}



Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}




int main() {
  string s;
  cin >> s;
  int n = s.size();
  if (n==2&&s[0]==s[1]) {
    cout << 1 << ' ' << 2 <<endl;
    return 0;
  }
  rep(i,n-2) {
    if (s[i]==s[i+1]||s[i]==s[i+2]) {
      cout << i+1 << ' ' << i+3 << endl;
      return 0;
    }
  }
  cout << -1 << ' ' << -1 << endl;
}

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

typedef long long ll;

ll n;
ll string_to_int(string x) {
	if (x == "") {
		return 0;
	}
	ll pn;
	stringstream s(x);
	s >> pn;
	return pn;
}
set<string> s;

void rec(string st) {
	if (string_to_int(st) > n) return ;
	s.insert(st);
	rec(st + "3");
	rec(st + "5");
	rec(st + "7");
}


int main() {
    cin >> n;
    rec("");
    int cnt = 0;
   // for (int i = 0; i < (int)s.size(); ++i) {
		//cout << s[i] << "\n";
    map<string,int> m;
	for (auto &x : s) {
		//cout << x << "\n";
		int five = 0, three = 0, seven = 0;
		for (int j = 0; j < (int)x.size(); ++j) {
			if (x[j] == '5') five++;
			if (x[j] == '3') three++;
			if (x[j] == '7') seven++;
			if (five && seven  && three && !m[x]) {
				//cout << x << "\n";
				cnt++;
				m[x] = 1;
			}
		}
	}
    cout << cnt;
}



Measured memory_bytes: 7956
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
#define LL long long
using namespace std;
const int N=1e5+10;
int n;
LL e,t,x[N],dp[N],tt=1e18;
template<typename I> inline void read(I &ot){
	I ch=getchar(), x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}
	ot=x*f;}
template<typename I, typename... U> inline void read(I &x,U&... y){read(x); read(y...);}
template<typename I>inline I mi(const I&a,const I&b){return a<b ? a : b;}
int main()
{
//	freopen("Shik and Game.in","r",stdin);
	//freopen(".out","w",stdout);
	read(n,e,t);
	for(int i=1;i<=n;i++) read(x[i]), dp[i]=2e9;
	for(int i=1,j=0;i<=n;i++)
	{
		while(2*(x[i]-x[j+1])>=t) 
		{
			tt=mi(tt,dp[j]-2*x[j+1]);
			j++;
		}
		dp[i]=mi(dp[j]+t,tt+2*x[i]);
	}
	printf("%lld\n",dp[n]+e);
	//fclose(stdin); fclose(stdout);
	return 0;
}


Measured memory_bytes: 1792
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  list($s) = explode(" ", trim(fgets(STDIN)));

  $PT = ['SS','WW','SW','WS'];
  for ($h=0; $h<count($PT); $h++) {
    $ans = [];
    $ans[0] = $PT[$h][0];
    $ans[1] = $PT[$h][1];
    // 3匹目～
    for ($i=2; $i<$n; $i++) {
      //o
      if($s[$i-1] == 'o'){  
        if($ans[$i-1] == 'S'){
          $ans[$i] = $ans[$i-2];
        }else{
          if($ans[$i-2] == 'S') {
            $ans[$i] = 'W';
          }else{
            $ans[$i] = 'S';
          }
        }
      }
      // x
      else{
        if($ans[$i-1] == 'S'){
          if($ans[$i-2] == 'S') {
            $ans[$i] = 'W';
          }else{
            $ans[$i] = 'S';
          }
        }else{
          $ans[$i] =  $ans[$i-2];
        }
      }      
    }
    
    $check1 = false;
    $check2 = false;
    if($s[0] == 'o'){
      if($ans[0] == 'S'){
        if($ans[1] == $ans[$n-1]){
          $check1 = true;
        }
      }else{
        if($ans[1] != $ans[$n-1]){
          $check1 = true;
        }
      }
    }else{
      if($ans[0] == 'W'){
        if($ans[1] == $ans[$n-1]){
          $check1 = true;
        }
      }else{
        if($ans[1] != $ans[$n-1]){
          $check1 = true;
        }
      }
    }

    if($s[$n-1] == 'o'){
      if($ans[$n-1] == 'S'){
        if($ans[$n-2] == $ans[0]){
          $check2 = true;
        }
      }else{
        if($ans[$n-2] != $ans[0]){
          $check2 = true;
        }
      }
    }else{
      if($ans[$n-1] == 'W'){
        if($ans[$n-2] == $ans[0]){
          $check2 = true;
        }
      }else{
        if($ans[$n-2] != $ans[0]){
          $check2 = true;
        }
      }
    }

    
    if($check1 && $check2){
      echo implode("", $ans);
      exit;
    }
  }
  echo "-1";

Measured memory_bytes: 21460
package main

import (
	"fmt"
	"sort"
)

func sale(n int, prices []int) int {
	sort.Ints(prices)
	subtotal := prices[len(prices)-1] / 2
	for _, v := range prices[:len(prices)-1] {
		subtotal += v
	}
	return subtotal
}

func main() {
	var n int
	fmt.Scan(&n)
	prices := make([]int, n)
	for i := range prices {
		fmt.Scan(&prices[i])
	}
	fmt.Println(sale(n, prices))
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
      int a;
      int b;
      int k;
      cin >> a;
      cin >> b;
      cin >> k;
      while(k > 0){
         if(k > 0){
          a = a / 2;
          b = b + a;
           k--;
         }
          if(k > 0){
          b = b / 2;
          a = a + b;
           k--;
         }
    }
       cout << a << " " << b << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
 
namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			string s = Console.ReadLine();
			int n = s.Length;

			var sb = new StringBuilder();
			for (int i = 0; i < n; i++) {
				if (s[i] == 'A') {
					sb.Append(s[i]);
				} else if (s[i] == 'B') {
					if (i < n - 1 && s[i + 1] == 'C') {
						sb.Append("D");
						++i;
					} else {
						sb.Append(s[i]);
					}
				} else {
					sb.Append(s[i]);
				}
			}

			string ss = sb.ToString();
			int m = ss.Length;

			long ans = 0;
			long aCount = 0;
			for (int i = 0; i < m; i++) {
				if (ss[i] == 'A') {
					++aCount;
				} else if (ss[i] == 'D') {
					ans += aCount;
				} else {
					aCount = 0;
				}
			}

			Console.WriteLine(ans);
		}
	}
}

Measured memory_bytes: 13212
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

        List<Integer> list = new ArrayList<>();
        list.add(s);
        int n = function(s);
        
        for (int i = 1; !list.contains(n); i++) {
            list.add(n);
            n = function(n);
        }
        System.out.println(list.size() + 1);
    }

    private static int function(int n) {
        if (n % 2 == 0) return n / 2;
        else return 3 * n + 1;
    }
}

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

int main() {
  int j,n,i,max=0,min=1000000000;
  int a[110];
  cin>>n;
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  for(i=0;i<n;i++){
    if(a[i]>max){
      max=a[i];
    }
    if(a[i]<min){
      min=a[i];
    }
  }
  j=max-min;
  cout<<j<<endl;
}



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

ll dp[102000][4];
int a[102000][4];
int n;
ll solve(int idx,int t){
    if(idx==n)
        return 0;
    
    if(dp[idx][t]!=-1)
        return dp[idx][t];
    for(int i=0;i<3;i++){
        if(t!=i)
            dp[idx][t] = max(dp[idx][t],solve(idx+1,i)+a[idx][i]);
    }
    return dp[idx][t];
}
int main(){
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
    }
    ll ans=0;
	for(int i=0;i<3;i++){
		ans=max(ans,solve(0,i));
    }
 
    cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 12800
#include <stdio.h>

int main(void) {

int a = 0;
int b = 0;
int c = 0;

scanf("%d %d %d",&a,&b,&c);

if (a < b && a < c) {
if (b < c) printf("%d %d %d\n",a,b,c);
if (c < b) printf("%d %d %d\n",a,c,b);
} else if (b < a && b < c) {
if (a < c) printf("%d %d %d\n",b,a,c);
if (c < a) printf("%d %d %d\n",b,c,a);
} else {
if (a < b) printf("%d %d %d\n",c,a,b);
if (b < a) printf("%d %d %d\n",c,b,a);
}

return 0;

}



Measured memory_bytes: 2056
#!/usr/bin/env python3
import sys


def solve(A: int, B: int, C: int, D: int):
    if A < C:
        ret = min(B - C, D - C)
    else:
        ret = min(D - A, B - A)
    ret = max(0, ret)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(A, B, C, D)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<vector>

using namespace std;

int main(){
    string S;
    cin >> S;
    int x = 0;
    for (int  i = 0; i < S.length(); i++)
    {
        if(S[i] == 'x') x++;
    }
    if(7 >= x){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio> 
//#include<vector>
//#include<string>
//#include<cstring>
//#include<algorithm> 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define  endl '\n'
#define all(s) s.begin(),s.end()
#define lowbit(x) (x&-x)
#define fi first
#define se second 
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f; 
const int N=2e5+10;
int main()
{
	int n,m,q,k;
	string s;
	cin>>s;
	s='.'+s;
	if(s[3]==s[4]&&s[5]==s[6]) cout<<"Yes";
	else cout<<"No"; 

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define _Pi 3.1415926535
#define _MOD = 1e9+7;
using namespace std;
typedef long long ll;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> l(n);
    rep(i,n) cin >> l[i];
    sort(l.begin(),l.end());

    cout << accumulate(l.begin()+n-k, l.end(), 0) << endl;;

    return 0;
}


Measured memory_bytes: 256
// #include "deque.h"
#include <iostream>
#include <vector>

long long score_difference(const std::vector<int>& sequence)
{
    std::vector<std::vector<long long>> dp(
        sequence.size(), std::vector<long long>(sequence.size()));

    bool first_player_turn{true};
    for (int left = sequence.size() - 1; left >= 0; --left) {
        for (int right = left; right < sequence.size(); ++right) {
            if (left == right)
                dp[left][right] = sequence[left];
            else
                dp[left][right] =
                    std::max(sequence[left] - dp[left + 1][right],
                             sequence[right] - dp[left][right - 1]);
        }
    }

    return dp.front().back();
}

int main(int argc, char* argv[])
{
    size_t seq_size;
    std::cin >> seq_size;
    std::vector<int> sequence(seq_size);
    for (size_t i = 0; i < seq_size; ++i) {
        int number;
        std::cin >> number;
        sequence[i] = number;
    }
    std::cout << score_difference(sequence) << std::endl;
    return 0;
}


Measured memory_bytes: 70656
#include <stdio.h>

int main()
{
	int i, N, A[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(A[i]));
	
	int L[200001] = {}, R[200001] = {};
	long long ans = 0;
	for (i = 1; i <= N; i++) {
		if (i - A[i] >= 1) L[i-A[i]]++;
		if (i + A[i] <= N) R[i+A[i]]++;
	}
	for (i = 1; i <= N; i++) ans += (long long)L[i] * R[i];
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 4032
import sys
import re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
    N = i_input()
    A = list(i_map())

    mod1 = 0
    for i in range(0,N):
        mod1 = (mod1+A[i]%MOD)%MOD
    
    mod1 = (mod1 * mod1)%MOD

    mod2 = 0
    for i in range(0,N):
        mod2 = (mod2+((A[i]*A[i])%MOD)%MOD)

    mod = (mod1-mod2)%MOD
    
    answer = ((500000004 * mod))% MOD

    print(answer)
    
    return

if __name__ == '__main__':
    main()

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

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

ll dp[55][55][2555];

void mod_add(ll &a, ll b){
	a += b;
	a %= MOD;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	ll n, score;cin >> n >> score;
	dp[0][0][0] = 1;
	ll nj, x;
	REP(i, n){
		REP(j, i+1)REP(k, score + 1){
			nj = j;
			mod_add(dp[i + 1][nj][k + 2 * nj], dp[i][j][k]);
			nj = j + 1;
			mod_add(dp[i + 1][nj][k + 2 * nj], dp[i][j][k]);
			nj = j;x = 2 * j;
			mod_add(dp[i + 1][nj][k + 2 * nj], dp[i][j][k] * x);
			nj = j - 1;x = j * j;
			if(j)mod_add(dp[i + 1][nj][k + 2 * nj], dp[i][j][k] * x);
		}
	}
	cout << dp[n][0][score] << endl;
	return 0;
}


Measured memory_bytes: 55552
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

//なんで解けたか
//何番目にあるかは対称性より関係ない
//枚数が0-3だけなので状態がまとめられる

//n枚で固定なので1個、2個、3個の枚数が決まればn-(i+j+k)で0個の皿の枚数が求まる
//状態を3つ持つだけでいい300^3=9*10^6くらいで余裕

//遷移を書いたときに、遷移元と遷移先に同じ項が出てくる
//どう解消するか→移項するだけ

int n;
double dp[310][310][310];
double rec(int i, int j, int k) {

	//メモってあればそれを使う
	if (dp[i][j][k] >=0)return dp[i][j][k];

	//境界条件すべて0の状態から0枚にするのは自明に0枚必要
	if (i == 0 && j == 0 && k == 0)return 0.0;

	double res = 0.0;

	//1枚使った状態 値×確率を集める
	if (i > 0)res += rec(i - 1, j, k)*i;//残り1枚の皿が1枚減る
	if (j > 0)res += rec(i + 1, j-1, k)*j;//残り2枚の皿が1枚減って、残り1枚になる
	if (k > 0)res += rec(i, j+1, k-1)*k;//残り3枚の皿が1枚減って、残り2枚の皿が1枚増える
	
	//+1にn/(i+j+k)をかけるとnになる。あとからまとめて(i+j+k)割るので、+n
	res += n;

	res *= 1.0 / (i + j + k);

	//メモして返す
	return dp[i][j][k] = res;
}

int main() {

	cin >> n;
	int one = 0;
	int two = 0;
	int three = 0;

	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (a == 1)one++;
		if (a == 2)two++;
		if (a == 3)three++;
	}

	memset(dp, -1, sizeof(dp));

	cout << fixed << setprecision(10) << rec(one, two, three) << endl;

	return 0;
}

Measured memory_bytes: 233088
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    ll a, b;
    cin >> a >> b;
    if (a * b <= 0) {
        cout << "Zero" << endl;
    } else {
        if (a > 0) {
            cout << "Positive" << endl;
        } else {
            if ((b - a + 1) % 2 == 0) {
                cout << "Positive" << endl;
            } else {
                cout << "Negative" << endl;
            }
        }
    }
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, K, p, m;
ll Plus[int(2e5 + 5)], Minus[int(2e5 + 5)];
ll ans = 1;

int main(){
  cin >> N >> K;
  for (int i = 0; i < N; i++){
    ll A; cin >> A;
    if (A >= 0) Plus[p] = A, p++;
    if (A < 0) Minus[m] = -1 * A, m++;
  }

  if (m == N && K % 2 != 0){
    sort(Minus, Minus + m);
    for (int i = 0; i < K; i++){
      ans *= Minus[i]; ans %= MOD;
    }
    ans *= -1;
    ans %= MOD; ans += MOD;
    cout << ans << endl;
    return 0;
  }

  if (p + m == N && N == K){
    for (int i = 0; i < p; i++){
      ans *= Plus[i]; ans %= MOD;
    }
    for (int i = 0; i < m; i++){
      ans *= -1 * Minus[i]; ans %= MOD; 
    }
    if (ans < 0) ans += MOD;
    cout << ans << endl;
    return 0;
  }

  sort(Plus, Plus + p, greater<ll>());
  sort(Minus, Minus + m, greater<ll>());


  int now = 0;
  for (int i = K - 1; i >= 1; i-=2){
    if (Minus[now] == 0 || Minus[now + 1] == 0) break;
    if (Minus[now] * Minus[now + 1] < Plus[i] * Plus[i-1]) break;

    Plus[i] = Minus[now];
    Plus[i-1] = Minus[now + 1];
    now += 2;
  }

  for (int i = 0; i < K; i++) ans *= Plus[i], ans %= MOD;
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 6736
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (a); i < n; i++)
#define print(x) cout << x << endl;
using namespace std;
typedef long long ll;

int main()
{
    int N;
    cin >> N;
    vector<int> X(N);
    rep(i, 0, N) cin >> X[i];

    int ans = 100100100;

    for (int i = 0; i < 100; i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) {
            sum += pow(X[j] - i, 2);
        }
        ans = min(ans, sum);
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
    ll n,W;
    cin>>n>>W;

    vector<ll> value(n),weight(n);
    ll V=0;
    for(int i=0;i<n;i++){
        cin>>weight[i]>>value[i];
        V+=value[i];
    }

    vector<vector<ll> > dp(n+1 , vector<ll>(V+1,10000000000));

    for(int i=0;i<=n;i++)   dp[i][0]=0;

    for(int i=1;i<=n;i++){
        for(int j=1;j<=V;j++){
            if(value[i-1] <=j ){
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i-1]]+weight[i-1]);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }

    ll res=0;

    for(int i=0;i<=V;i++){
        if(dp[n][i]<=W) res=i;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 80256
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define mod 998244353
#define maxn 10000010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
ll fac[maxn],inv[maxn],p2[maxn],p3[maxn];
int n;
ll C(int n,int m){return (n<0||m<0||m>n)?0:fac[n]*inv[m]%mod*inv[n-m]%mod;}
ll power(ll a,ll b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)ans=ans*a%mod;
	return ans;
}
int main()
{
	n=read();
	inv[1]=1;
	for(int i=2;i<=n;i++)
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	inv[0]=fac[0]=p2[0]=p3[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*i%mod;
		inv[i]=inv[i-1]*inv[i]%mod;
		p2[i]=p2[i-1]*2%mod; p3[i]=p3[i-1]*3%mod;
	}
	ll ans=p3[n];
	for(int i=n/2+1;i<=n;i++)
		ans=(ans-2*C(n,i)*p2[n-i]%mod+mod)%mod;
	writeln(ans);
	return 0;
}

Measured memory_bytes: 312704
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[200005],xorsum,digsum,ed;
long long ans;
int main(){
	scanf("%d",&n);
	for(register int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(register int i=1;i<=n;i++){
		while((xorsum^a[ed+1])==digsum+a[ed+1]&&ed<n){
			ed++;
			xorsum^=a[ed];digsum+=a[ed];
		}
		ans+=(ed-i+1);
		xorsum^=a[i];
		digsum-=a[i];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 4604
package main

import (
	"fmt"
)

func main() {
	var H, W int
	fmt.Scan(&H, &W)
	A := make([][]byte, H)
	for i := 0; i < H; i++ {
		var low string
		fmt.Scan(&low)
		A[i] = []byte(low)
	}

	flagsH := make([]bool, H)
	flagsW := make([]bool, W)

	for i := 0; i < H; i++ {
		for _, b := range A[i] {
			if b == '#' {
				flagsH[i] = true
				break
			}
		}
	}

	for i := 0; i < W; i++ {
		for j := 0; j < H; j++ {
			if A[j][i] == '#' {
				flagsW[i] = true
				break
			}
		}
	}

	for i := 0; i < H; i++ {
		if !flagsH[i] {
			continue
		}

		var row string
		for j := 0; j < W; j++ {
			if !flagsW[j] {
				continue
			}
			row += string(A[i][j])
		}
		fmt.Println(row)
	}
}


Measured memory_bytes: 1152
N, K = map(int, input().split())
h = [int(x) for x in input().split()]
dp = [10**10] * N
dp[0] = 0
for i in range(1, N):
    for j in range(1, K+1):
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[-1])

Measured memory_bytes: 52448
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

struct HopcroftKarp {
	int n;
	vector<vector<int>> g;
	vector<int> match, dist;
	vector<bool> used, alive;
	HopcroftKarp(int n) : n(n), g(n), match(n), dist(n), used(n), alive(n, true) {}
	void addEdge(int u, int v) {
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	int maximumMatching() {
		int cnt = 0;
		fill(match.begin(), match.end(), -1);
		while (true) {
			buildAlternatingLevelGraph();
			fill(used.begin(), used.end(), false);
			int flow = 0;
			for (int u = 0; u < n; u++) {
				if (!alive[u])continue;
				if (match[u] == -1 && augment(u))
					flow++;
			}
			if (flow == 0)break;
			cnt += flow;
		}
		return cnt;
	}
	void buildAlternatingLevelGraph() {
		fill(dist.begin(), dist.end(), -1);
		queue<int> q;
		for (int u = 0; u < n; u++)
			if (match[u] == -1) {
				q.emplace(u);
				dist[u] = 0;
			}
		while (q.size()) {
			int u = q.front(); q.pop();
			for (int v : g[u]) {
				int w = match[v];
				if (w != -1 && dist[w] == -1) {
					dist[w] = dist[u] + 1;
					q.emplace(w);
				}
			}
		}
	};
	bool augment(int u) {
		used[u] = true;
		for (int v : g[u]) {
			if (!alive[v])continue;
			int w = match[v];
			if (w == -1 || (!used[w] && dist[w] == dist[u] + 1 && augment(w))) {
				match[u] = v;
				match[v] = u;
				used[v] = true;
				return true;
			}
		}
		return false;
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	HopcroftKarp hk(N + M);
	rep(i, 0, N) {
		int K; cin >> K;
		rep(j, 0, K) {
			int b; cin >> b; b--;
			hk.addEdge(i, N + b);
		}
	}
	int res = hk.maximumMatching();
	if (res == M) {
		cout << "Bob" << endl;
	}
	else {
		cout << "Alice" << endl;
	}
	return 0;
}

Measured memory_bytes: 4816
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i] = -A[i];
  }

  map<ll,ll> cnt;
  for (int i = 0; i < N; i++) {
    cnt[A[i]]++;
  }

  vector<ll> S;
  for(auto e: cnt) {
    while(e.second >= 2) {
      e.second -= 2;
      S.push_back(-e.first);
      if (S.size() >= 2) break;
    }
    if (S.size() >= 2) break;
  }
  if (S.size() < 2) {
    cout << 0 << endl;
  } else {
    cout << S[0] * S[1] << endl;
  }

  return 0;
}

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void print(H head) { cout << head << endl; }
template<typename H, typename ...T> void print(H head, T ...tail) { cout << head << " "; print(tail...); }

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n, c, k; read(n, c, k);
	vector<int> v(n);
	rep(i, 0, n) read(v[i]);

	sort(all(v));

	int st = 0, ans = 1;
	rep(i, 1, n) {
		if (i - st >= c || v[i] - v[st] > k) {
			st = i;
			ans++;
		}
	}

	print(ans);
}


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

using namespace std;

#define FOR(i, j, k, in) for (int i = j; i < k; i += in)
#define RFOR(i, j, k, in) for (int i = j; i >= k; i -= in)
#define REP(i, j) FOR(i, 0, j, 1)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define MP make_pair
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
const double pi = acos(-1.0);
typedef pair<int, int> PII;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int uint64;

#define IOS                           \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

int dp[3000 + 1][3000 + 1];
int bt[3000 + 1][3000 + 1][2];

int main()
{
    IOS
        string a,
        b;
    cin >> a >> b;
    REP(i, a.size() + 1)
    {
        if (i == 0)
            continue;
        REP(j, b.size() + 1)
        {
            if (j == 0)
                continue;
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (dp[i][j] == dp[i - 1][j])
                bt[i][j][0] = i - 1, bt[i][j][1] = j;
            else
                bt[i][j][0] = i, bt[i][j][1] = j - 1;
            if (a[i - 1] == b[j - 1] && dp[i][j] < 1 + dp[i-1][j-1])
            {
                dp[i][j]++;
                bt[i][j][0] = i-1, bt[i][j][1]=j-1;
            }
        }
    }

    // REP(i, a.size() + 1)
    // {
    //     REP(j, b.size() + 1)
    //     {
    //         cout << bt[i][j][0] << ":" << bt[i][j][1] << " ";
    //     }
    //     cout << "\n";
    // }

    // REP(i, a.size() + 1)
    // {
    //     REP(j, b.size() + 1)
    //     {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    string s = "";

    int i = a.size(), j = b.size();
    while (i != 0 && j != 0)
    {
        // cout << i << " " << j << "\n";
        int bi = bt[i][j][0], bj = bt[i][j][1];
        // cout << dp[i][j] << " " << dp[bi][bj] << "\n";
        if (dp[bi][bj] != dp[i][j])
            s += a[i - 1];
        i = bi, j = bj;
        // cout << i << " " << j << "\n";
    }
    reverse(s.begin(), s.end());

    cout << s;
}

Measured memory_bytes: 105856
while True:
    H,W = map(int,input().split())
    if H == 0 and W == 0:
        break
    else:
        for i in range(H):
            if i % 2 == 0:
                if W % 2 == 0:
                    print('#.'*(int(W/2)))
                else:
                    print('#.'*(int(((W-1)/2))),'#',sep='')
            else:
                if W % 2 == 0:
                    print('.#'*int((W/2)))
                else:
                    print('.#'*(int(((W-1)/2))),'.',sep='')
    print('')  


Measured memory_bytes: 5616
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 1e5 + 5;

int n, m;
int a[maxn], dp[maxn];

int main(){
	scanf("%d%d", &n, &m);
	FOR(i, 0, m){
		int x; scanf("%d", &x);
		a[x] = true;
	}
	dp[0] = 1;
	REP(i, 1, n){
		(dp[i] += dp[i - 1]) %= INF;
		if(i > 1) (dp[i] += dp[i - 2]) %= INF;
		if(a[i])
			dp[i] = 0;
	}
	printf("%d\n", dp[n]);
	return 0;
}



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

const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}comb(200005);


int main()
{
    int n,m,k;
    cin >> n >> m >> k;
    mint ans = 0;
    mint col = m;
    for(int i=n-1; i>=0; i--){
        mint now = col;
        now *= comb(n-1,i);
        if(i <= k) ans += now;
        col *= m-1;
    }

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

Measured memory_bytes: 6204
#include <iostream>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)
#define myforInv(i,N) for(i=N;i>=0;i--)
#define myforFLInv(i,f,l) for(i=f;i>l;i--)

using namespace std;
int main(){
	long N,W,i,j;
	long w[100],v[100],dp[100001]={};

	cin >> N >> W;
	myfor(i,N){
		cin >> w[i]>>v[i];
	}
	myfor(i,N)myforFLInv(j,W,w[i]-1){
		dp[j] = max(dp[j-w[i]] + v[i],dp[j]);
	}
	cout << dp[W] << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

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

	std::vector<std::pair<char, i64>> vec;
	for(int i = 0; i < s.size(); i++) {
		if(vec.empty() or vec.back().first != s[i]) vec.push_back({s[i], 1});
		else vec.back().second++;
	}
	
	if(vec.size() == 1) {
		printf("%lld\n", vec[0].second * (vec[0].second + 1) / 2);
		return 0;
	}

	i64 ans = 0;
	if(vec.front().first == '>') {
		ans += vec.front().second * (vec.front().second + 1) / 2;
		vec.erase(begin(vec));
	}
	if(vec.back().first == '<') {
		ans += vec.back().second * (vec.back().second + 1) / 2;
	}
	for(int i = 0; i + 1 < vec.size(); i += 2) {
		if(vec[i].second >= vec[i + 1].second) {
			ans += vec[i].second * (vec[i].second + 1) / 2;
			ans += vec[i + 1].second * (vec[i + 1].second - 1) / 2;
		} else {
			ans += vec[i].second * (vec[i].second - 1) / 2;
			ans += vec[i + 1].second * (vec[i + 1].second + 1) / 2;
		}
	}

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


Measured memory_bytes: 6904
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int L, R;
    cin >> L >> R;

    int l, r;
    l = L % 2019;
    r = R % 2019;

    int ans;
    int min = 2019;
    if (l >= r)
    {
        min = 0;
    }
    else
    {
        if ((R-L) >= 2019)
        {
            min = 0;
        }
        else
        {
            for (int i = l; i < r; i++)
            {
                for (int j = i + 1; j <= r; j++)
                {
                    ans = (i * j) % 2019;
                    if (min >= ans)
                    {
                        min = ans;
                    }
                    if (min == 0)
                    {
                        break;
                    }
                }
            }
        }
    }
    cout << min << endl;
}

Measured memory_bytes: 256
{-# LANGUAGE BangPatterns #-}
import Data.Int
import Data.List
import qualified Data.ByteString.Char8 as BS
import qualified Data.Map.Strict as Map

data Drink = Drink {-# UNPACK #-} !Int64 {-# UNPACK #-} !Int deriving (Eq,Ord)

main = do
  [n,m] <- map (read . BS.unpack) . BS.words <$> BS.getLine
  ab <- fmap sort $ sequence $ replicate n $ do
    [a,b] <- map (read . BS.unpack) . BS.words <$> BS.getLine
    return (Drink a (fromIntegral b)) -- (a :: Int64, b :: Int64)
  let solve !k !yen (Drink a b : xs) | k <= b = yen + a * fromIntegral k
                                     | otherwise = solve (k - b) (yen + a * fromIntegral b) xs
  print $ solve m 0 ab


Measured memory_bytes: 49404
import math
N, D = map(int, input().split())
count = 0
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]
for i in range(N):
  if math.sqrt(x[i] * x[i] + y[i] * y[i]) <= D:
    count += 1
print(count)

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

int main() {
  int a;
  cin >> a;
  cout << a /100 + ((a - a / 100 * 100) / 10) + (a - a / 100 * 100 -((a - a / 100 * 100) / 10) * 10)    << endl;
}


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

using namespace std;

typedef long long ll;

int N, M, X;
int cost[12], A[12][12];

int main() {
	cin >> N >> M >> X;
	int ans = 1145141919;
	for (int i = 0; i < N; i++) {
		cin >> cost[i];
		for (int j = 0; j < M; j++)cin >> A[i][j];
	}

	for (int bit = 0; bit < (1 << N); bit++) {
		vector<int> jukuren(M, 0);
		int total = 0;
		for (int i = 0; i < N; i++) {
			if ((bit >> i) & 1) {
				total += cost[i];
				for (int j = 0; j < M; j++)jukuren[j] += A[i][j];
			}
		}
		bool f = true;
		for (int i = 0; i < M; i++)if (jukuren[i] < X)f = false;
		if (f) ans = min(ans, total);
	}
	if (ans == 1145141919)cout << -1 << endl;
	else cout << ans << endl;
	return 0;
}

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



int main(){
    int N;
    cin >> N;
    double ans = (N/2 + N%2) / (double)N;
    printf("%.10lf\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  vector<vector<int>> data(N - 1, vector<int> (3, 0));
  for (int i = 0; i < N - 1; i++) {
    cin >> data.at(i).at(0) >> data.at(i).at(1) >> data.at(i).at(2);
  }
  int ans;
  for (int i = 0; i < N - 1; i++) {
    ans = 0;
    for (int j = i; j < N - 1; j++) {
      if (data.at(j).at(1) > ans) ans += data.at(j).at(1) - ans;
      if (ans % data.at(j).at(2) == 0) ans += data.at(j).at(0);
      else ans += (data.at(j).at(2) - ans % data.at(j).at(2)) + data.at(j).at(0);
    }
    cout << ans << endl;
  }
  cout << 0 << endl;
  return 0;
}


Measured memory_bytes: 256