84902024-01-18 21:21:45zoliFestés (50 pont)cpp11Wrong answer 48/50352ms23996 KiB
#include <iostream>
#include<climits>
using namespace std;
int N,M;
int r[5]; ///sorok ajanlata
int c[100001][5][5]; /// c[j][x][y] => j. oszlop ajanlata x, y kozott
void be()
{
    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>r[i];
    for(int j=1;j<=M;j++)
        for(int x=1;x<=N;x++)
            for(int y=x;y<=N;y++) cin>>c[j][x][y];
}
void megold()
{
    long long sum;
    long long mini=0;
    /// ha minden sor festve van
    for(int i=1;i<=N;i++) mini+=r[i];

    if(N==2) ///csak 2 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][1][1]+c[j][2][2],c[j][1][2]);
             if(sum>=mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][2][2],c[j][1][2]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(c[j][1][1],c[j][1][2]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

    }
    else if(N==3) /// 3 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3],c[j][1][1]+c[j][2][3]),
                              c[j][1][2]+c[j][3][3]),c[j][1][3]),c[j][1][2]+c[j][2][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(c[j][2][2]+c[j][3][3],c[j][2][3]),c[j][1][2]+c[j][3][3]),
                          c[j][1][3]),c[j][1][2]+c[j][2][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(c[j][1][1]+c[j][3][3],c[j][1][1]+c[j][2][3]),
                              c[j][1][2]+c[j][3][3]),c[j][1][3]),c[j][1][2]+c[j][2][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R3 sor festve van
        sum=r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(c[j][1][1]+c[j][2][2],c[j][1][2]),c[j][1][1]+c[j][2][3]),
                      c[j][1][3]),c[j][1][2]+c[j][2][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 es R2 festve van, R3 nincs
        sum=r[1]+r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(c[j][3][3],c[j][2][3]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 es R3 festve van, R2 nincs
        sum=r[1]+r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(c[j][2][2],c[j][2][3]),c[j][1][2]),c[j][1][3]),c[j][1][2]+c[j][2][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 es R3 festve van, R1 nincs
        sum=r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(c[j][1][1],c[j][1][2]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig
    }
    else /// N==4 sor van
    {
        /// nincs sor festve
        sum=0;
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1 sor festve van
        sum=r[1];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(min(min(min(c[j][2][2]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][2][3]+c[j][4][4]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][2][4]),
                c[j][2][3]+c[j][3][4]), c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2 sor festve van
        sum=r[2];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][3][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R3 sor festve van
        sum=r[3];
        for(int j=1;j<=M;j++)
        {
             sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][3]+c[j][4][4]),c[j][1][1]+c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R4 sor festve van
        sum=r[4];
        for(int j=1;j<=M;j++)
        {
              sum+=min(min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][2][2]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][1][1]+c[j][2][3]),c[j][1][1]+c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][3]),c[j][1][1]+c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R2 sor festve van
        sum=r[1]+r[2];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][3][3]+c[j][4][4],c[j][1][4]),
                c[j][2][3]+c[j][4][4]),c[j][3][4]),
                 c[j][1][3]+c[j][4][4]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R3 sor festve van
        sum=r[1]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][2][2]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][2][3]+c[j][4][4]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][2][4]),
                c[j][1][2]+c[j][2][3]+c[j][4][4]),c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R4 sor festve van
        sum=r[1]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][2][2]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][2][3]),c[j][2][2]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][2][4]),
                c[j][1][2]+c[j][2][3]),c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R3 sor festve van
        sum=r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][4][4],c[j][1][4]),
                c[j][1][2]+c[j][4][4]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]+c[j][4][4]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R4 sor festve van
        sum=r[2]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(min(min(min(min(min(min(min(c[j][1][1]+c[j][3][3],c[j][1][4]),
                c[j][1][2]+c[j][3][3]),c[j][1][1]+c[j][2][3]),c[j][1][1]+c[j][3][4]),
                c[j][1][2]+c[j][3][4]), c[j][1][3]), c[j][1][1]+c[j][2][4]),
                c[j][1][2]+c[j][2][3]),c[j][1][1]+c[j][2][3]+c[j][3][4]),
                c[j][1][2]+c[j][2][4]),c[j][1][3]+c[j][3][4]),c[j][1][3]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig


        /// R3+R4 sor festve van
        sum=r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][1][1]+c[j][2][2],c[j][1][4]),
                c[j][1][2]),c[j][1][1]+c[j][2][3]),
                 c[j][1][3]), c[j][1][1]+c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig


        /// R1+R2+R3 sor festve van
        sum=r[1]+r[2]+r[3];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(c[j][4][4],c[j][1][4]),c[j][3][4]),c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R2+R4 sor festve van
        sum=r[1]+r[2]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][3][3],c[j][1][4]),
                c[j][2][3]),c[j][3][4]),
                 c[j][1][3]),c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R1+R3+R4 sor festve van
        sum=r[1]+r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(min(min(c[j][2][2],c[j][1][4]),
                c[j][1][2]),c[j][2][3]),
                 c[j][1][3]), c[j][2][4]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig

        /// R2+R3+R4 sor festve van
        sum=r[2]+r[3]+r[4];
        for(int j=1;j<=M;j++)
        {
               sum+=min(min(min(c[j][1][1],c[j][1][4]),c[j][1][2]),c[j][1][3]);
             if(sum>mini) break; /// ha menet kozben tobbe kerulne, mint az eddigi legolcsobb lehetoseg
        }
        if(sum<mini) mini=sum; /// ez festesi mod az olcsobb eddig
    }
    cout<<mini;
}
int main()
{
    be();
    megold();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base48/50
1Accepted0/03ms1752 KiB
2Accepted0/03ms1920 KiB
3Accepted2/2209ms21776 KiB
4Accepted2/23ms2324 KiB
5Accepted3/34ms2572 KiB
6Accepted2/228ms4560 KiB
7Accepted2/2293ms22280 KiB
8Accepted2/2289ms22136 KiB
9Accepted2/2291ms22408 KiB
10Accepted2/2303ms22532 KiB
11Accepted2/2303ms22672 KiB
12Accepted2/2270ms21096 KiB
13Accepted2/2289ms20976 KiB
14Accepted2/2101ms22820 KiB
15Accepted3/3104ms23032 KiB
16Accepted3/3180ms23004 KiB
17Accepted2/2181ms23344 KiB
18Accepted3/3174ms23024 KiB
19Accepted2/2246ms21332 KiB
20Accepted2/2270ms22268 KiB
21Accepted2/2287ms23444 KiB
22Accepted2/2287ms23756 KiB
23Accepted2/2289ms23996 KiB
24Accepted2/2280ms23860 KiB
25Wrong answer0/2352ms23724 KiB